Đề thi chọn học sinh giỏi lớp 09 THCS - Môn Tin

Nội dung text: Đề thi chọn học sinh giỏi lớp 09 THCS - Môn Tin

1. UBND HUYỆN BÌNH XUYÊN KỲ THI CHỌN HSG LỚP 09 THCS NĂM HỌC 2017-2018 PHÒNG GD VÀ ĐT ĐỀ THI MÔN: TIN HỌC Thời gian làm bài: 150 phút, không kể thời gian giao đề. ĐỀ CHÍNH THỨC (Đề thi có 02 trang, gồm 03 bài) TỔNG QUAN ĐỀ THI Tên chương File dữ liệu File dữ liệu Time / Bài Tên bài Điểm trình vào ra 1 test 1 Số nguyên tố Prime.pas Prime.inp Prime.out 1 giây 4.0 2 Cắt chữ vi tính Cutword.pas Cutword.inp Cutword.out 1 giây 3.0 3 Tìm số Find.pas Find.inp Find.out 1 giây 3.0 Sử dụng ngôn ngữ lập trình Turbo Pascal hoặc Free Pascal giải các bài toán sau: Bài 1: Số nguyên tố Số nguyên tố là số tự nhiên có hai ước là 1 và chính nó. Yêu cầu: Hãy đếm các số nguyên tố trong khoảng [2,푛]. Dữ liệu: Gồm 1 dòng duy nhất chứa số nguyên dương n (với 2 ≤ 푛 < 108) Kết quả: Gồm 1 dòng duy nhất chứa số lượng các số nguyên tố trong đoạn [2,푛]. Ví dụ: Test Prime.inp Prime.out 1 2 1 2 10 4 Ràng buộc: - Có 60% số test ứng với 60% số điểm của bài thỏa mãn điều kiện:2 ≤ 푛 ≤ 105; - Có 40% số test còn lại ứng với 40% số điểm của bài thỏa mãn điều kiện: 105 < 푛 < 108. Bài 2: Cắt chữ vi tính Trong kỳ thi học sinh giỏi cấp huyện năm 2017, ban tổ chức có ý định in vi tính số báo danh của từng thí sinh, sau đó dán lên từng bàn, để các em biết vị trí ngồi của mình. Chữ số vi tính là các số 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, được in ra trên các miếng đề can, và dán được lên mặt bàn. Số báo danh của thí sinh được kết hợp từ các chữ số vi tính đó, ví dụ số báo danh 168 được kết hợp từ 3 chữ số vi tính là 1, 6, và 8. Số báo danh của thí sinh được đánh từ 1 đến n, trong đó n là số học sinh tham gia. Số lượng chữ số vi tính được in ra càng nhiều, kinh phí càng lớn. Ban tổ chức muốn biết tổng số chữ vi tính sẽ được in ra, để có thể dự trù kinh phí. Ví dụ: nếu có 13 thí sinh tham dự thì số báo danh cần đánh là 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, như vậy cần dùng đến 17 chữ số vi tính. Tuy nhiên, do lượng thí sinh quá đông, việc đếm tổng số chữ vi tính cần phải in ra không thể nhanh được. Yêu cầu: Em hãy lập trình giúp ban tổ chức đếm tổng số chữ vi tính cần phải in. 1
2. Dữ liệu: Dòng đầu tiên chỉ chứa duy nhất một số N (1 ≤ 푛 ≤ 1016) là số thí sinh sẽ tham dự kỳ thi. Kết quả: Đưa ra tổng số chữ số vi tính cần in ra. Ví dụ: Test Cutword.inp Cutword.out 1 4 4 2 13 17 Ràng buộc: - Có 60% số test tương ứng với 푛 ≤ 107 - Có 40% số test tương ứng với 푛 > 107 Bài 3: Tìm số Khi đếm số chữ số của một số nguyên dương, ta không đếm bất kì chữ số 0 nào ở trước chữ số khác 0 đầu tiên của số nguyên dương đó. Ví dụ: Số 0034 là số có đúng 2 chữ số. Cho hàm số f(n) như sau: f(1) = c với c là số nguyên dương; f(n) = m.f(n-1) với n, m là các số nguyên dương (với n > 1). Yêu cầu: Cho hai số nguyên dương k và p. Tìm số nguyên dương N nhỏ nhất thỏa mãn đồng thời ba điều kiện (1), (2), (3) sau đây: (1): Số f(n) có ít nhất k chữ số và nhiều nhất (k + 50) chữ số. (2): Tổng tất cả các chữ số của số f(n) là số chẵn. (3): Số f(n) có ít nhất p chữ số lẻ. Dữ liệu: Gồm một dòng duy nhất lần lượt chứa các số c, m, k, p. Các số cách nhau ít nhất một khoảng trắng (dấu cách). Kết quả: Gồm 1 dòng duy nhất chứa giá trị N tìm được, hoặc ghi số 0 nếu không tồn tại số n. Ví dụ: Test Find.inp Find.out 1 3 2 2 1 7 2 3 1 2 1 0 Ràng buộc: - Có 30% số test có c < 101, m < 101, k < 5, p < 5. - Có 70% số test có c < 10001, m < 10001, k < 151, p < 201. HẾT 2