HSG THCS cấp tỉnh 2020-2021 (ngày thi 16/03/2021)

(bản chụp không thấy tên Sở GD&ĐT)
ĐỀ CHÍNH THỨC

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH Năm học 2020 - 2021
Môn: Tin học - Ngày thi: 16/03/2021
(Đề thi gồm: 04 trang, 05 bài)

---

Ghi chú

Bản chụp đề trong tài liệu sưu tầm bị cắt mất phần tên Sở GD&ĐT nên chưa xác định được tỉnh. Nếu bạn biết đề này của tỉnh nào, hãy góp ý để chúng tôi cập nhật.

Tổng quan bài thi

Bài	Tệp chương trình	Dữ liệu vào	Dữ liệu ra	Điểm
1	BAI01.*	BAI01.INP	BAI01.OUT	4,0
2	BAI02.*	BAI02.INP	BAI02.OUT	4,0
3	BAI03.*	BAI03.INP	BAI03.OUT	4,0
4	BAI04.*	BAI04.INP	BAI04.OUT	4,0
5	BAI05.*	BAI05.INP	BAI05.OUT	4,0

Học sinh có thể sử dụng ngôn ngữ lập trình Pascal hoặc C++ để giải các bài toán. Khi đó dấu * trong Tệp chương trình sẽ là pas hoặc cpp.

Bài 1. Bắt tay (4,0 điểm)

Trong hội nghị tuyên dương các bạn học sinh giỏi cấp tỉnh năm 2020, có n học sinh tham dự mọi người gặp nhau chào hỏi và bắt tay nhau. Biết rằng mỗi học sinh bắt tay với tất cả những học sinh còn lại và 2 người bất kỳ chỉ được bắt tay nhau đúng 1 lần.

Yêu cầu: Em hãy đếm số lượng cái bắt tay?

Dữ liệu vào: Đọc dữ liệu vào từ tệp BAI01.INP là một số nguyên dương n (1 ≤ n ≤ 10⁶).

Dữ liệu ra: Ghi kết quả ra tệp BAI01.OUT là số lượng cái bắt tay.

Ví dụ:

BAI01.INP	BAI01.OUT
1	0
2	1
3	3
4	6
5	10

Giải thích: Có 1 người thì có 0 cái bắt tay, có 2 người có 1 cái bắt tay, 3 người có 3 cái bắt tay.

Bài 2. Số đảo nguyên tố (4,0 điểm)

Cho số nguyên dương N, khi đảo ngược trật tự các chữ số của N ta sẽ thu được một số nguyên dương M, M được gọi là số đảo ngược của N.

Ví dụ: N = 613 thì M = 316 là số đảo ngược của N.

Số nguyên dương M được gọi là số nguyên tố nếu nó chỉ có hai ước số là 1 và chính nó, số 1 không phải là số nguyên tố.

Cho hai số nguyên dương P và Q với 0 < P < Q ≤ 10⁵.

Yêu cầu: Hãy tìm tất cả các số nguyên dương N thỏa mãn P ≤ N ≤ Q mà số đảo ngược của số N là số nguyên tố.

Dữ liệu vào: Đọc dữ liệu vào từ tệp BAI02.INP: Một dòng ghi hai số nguyên dương P Q, hai số được ghi cách nhau ít nhất một dấu cách.

Kết quả ra: Ghi kết quả ra tệp BAI02.OUT: Gồm nhiều dòng, mỗi dòng ghi một số nguyên N tìm được.

Ví dụ:

BAI02.INP	BAI02.OUT
10 19	11 13 14 16 17

Bài 3. Ghép hình (4,0 điểm)

Có N tấm ván đều có chiều rộng là 1. Các tấm ván được đánh số thứ tự từ 1 đến N, chiều dài tấm ván thứ i là aᵢ. Người ta muốn ghép các tấm ván này thành một bàn hình vuông với diện tích lớn nhất có thể mà không sử dụng các đoạn sau khi cắt bỏ hoặc quay ngang tấm ván. Cho biết độ dài của N tấm ván.

Yêu cầu: Em hãy viết chương trình tìm kích thước hình vuông có diện tích lớn nhất.

Dữ liệu vào: Từ tệp BAI03.INP

• Dòng đầu tiên là số nguyên dương N.
• Dòng thứ 2 là dãy số nguyên dương độ dài các tấm ván: a₁, a₂, …, aₙ (N ≤ 10⁶, 0 < aᵢ ≤ 10⁶).

Dữ liệu ra: Ghi ra tệp BAI03.OUT: Một số duy nhất là kích thước của mặt bàn hình vuông lớn nhất.

Ví dụ:

BAI03.INP	BAI03.OUT	Giải thích
5 4 3 1 4 5	3	Chọn 3 tấm có độ dài 4, 3, 5 để ghép thành hình vuông 3x3
4 4 4 4 4	4	Có 4 tấm ván độ dài 4 nên ta ghép được hình vuông 4x4 và không có ván thừa.
3 1 1 1	1	Có 3 tấm độ dài 1 nên ta chỉ có thể chọn 1 tấm để ghép 1x1
5 5 5 1 1 5	3	Chọn 3 tấm độ dài 5 để ghép thành hình vuông 3x3

Ràng buộc:

• Có 75% số điểm với N ≤ 10³.
• Có 25% số điểm còn lại N ≤ 10⁶.

Bài 4. Tìm tên duy nhất (4,0 điểm)

Tên của học sinh là tập hợp liên tiếp các chữ in thường và không chứa khoảng trắng. Cho trước một danh sách liên tiếp tên các bạn học sinh được viết cách nhau một dấu cách. Tên được gọi là đối xứng nếu viết theo chiều ngược lại vẫn là tên ban đầu.

Yêu cầu: Em hãy lập trình in ra số lượng các tên chỉ xuất hiện một lần và tên đối xứng trong danh sách đã cho.

Dữ liệu vào: Đọc dữ liệu vào từ tệp BAI04.INP: Một dòng duy nhất chứa xâu đầu vào là các tên của học sinh, dữ liệu đảm bảo các tên chỉ gồm các chữ cái in thường.

Kết quả ra: Ghi kết quả ra tệp BAI04.OUT

• Dòng 1: Ghi số lượng các tên chỉ xuất hiện một lần.
• Dòng 2: Ghi số lượng tên đối xứng.

Ví dụ:

BAI04.INP	BAI04.OUT	Giải thích
kien mai hong anh mai ha hong anh linh ha mai thao aabaa mai aabaa	3 2	Có 3 tên xuất hiện một lần là kien, linh, thao, 2 tên đối xứng aabaa
kien thang kien thang	0 0	Không có tên nào xuất hiện một lần, không có tên đối xứng

Ràng buộc:

• Có 75% số điểm với số lượng tên ≤ 10³.
• Có 25% số điểm còn lại với số lượng tên ≤ 10⁵.

Chú ý: Thí sinh làm đúng ½ yêu cầu của bài sẽ được ½ số điểm.

Bài 5. Dãy số (4,0 điểm)

Bạn Mai là học sinh đội tuyển Tin nhưng lại rất giỏi toán, một hôm Mai đố các bạn trong đội tuyển Tin hai bài toán như sau:

Bài toán 1: Hàm Rev(x) được xác định bằng cách đảo ngược thứ tự các chữ số trong x. Cho dãy số nguyên được xác định như sau:

• A₁ = 1
• Aₙ = Rev(Aₙ₋₁) + 2

Vậy dãy A gồm các số: 1 3 5 7 9 11 13 33 …

Yêu cầu: Cho trước một số nguyên dương K, hãy tìm số A_K của dãy số trên. Ví dụ: Với K = 5 ta có số cần tìm là 9.

Bài toán 2: Cho một dãy gồm tất cả các số nguyên dương lẻ không chia hết cho 5 và được sắp xếp tăng dần: A₁ = 1, A₂ = 3, A₃ = 7, A₄ = 9, A₅ = 11, …

Yêu cầu: Cho trước một số nguyên dương K, hãy tìm số A_K của dãy số trên. Ví dụ: Với K = 5 ta có số cần tìm là 11.

Em hãy lập trình đưa ra các số mà bạn Mai yêu cầu ở hai bài toán trên.

Dữ liệu vào: Đọc dữ liệu vào từ tệp BAI05.INP: Một dòng duy nhất là số K.

Kết quả ra: Ghi kết quả ra tệp BAI05.OUT

• Dòng 1: Ghi số thứ K của bài toán 1.
• Dòng 2: Ghi số thứ K của bài toán 2.

Ví dụ:

BAI05.INP	BAI05.OUT	Giải thích
5	9 11	Số thứ 5 của bài toán 1 là 9 Số thứ 5 của bài toán 2 là 11
6	11 13	Số thứ 6 của bài toán 1 là 11 Số thứ 6 của bài toán 2 là 13
8	33 19	Số thứ 8 của bài toán 1 là 33 Số thứ 8 của bài toán 2 là 19

Ràng buộc:

• Có 75% số điểm với K ≤ 10⁶.
• Có 25% số điểm còn lại K ≤ 10¹².

Chú ý: Thí sinh làm đúng ½ yêu cầu của bài sẽ được ½ số điểm.

---

• Thí sinh không sử dụng tài liệu
• Cán bộ coi thi không giải thích gì thêm