Đề thi học sinh giỏi môn Tin học Lớp 9 - Năm học 2022-2023 - Sở GD&ĐT Ninh Bình (Có đáp án)

Nội dung text: Đề thi học sinh giỏi môn Tin học Lớp 9 - Năm học 2022-2023 - Sở GD&ĐT Ninh Bình (Có đáp án)

1. SỞ GIÁO DỤC VÀ ĐÀO TẠO ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 9 THCS CẤP TỈNH TỈNH NINH BÌNH NĂM HỌC 2022-2023 Môn: TIN HỌC Ngày thi: 14/02/2023 ĐỀ THI CHÍNH THỨC Thời gian làm bài:150 phút (không kể thời gian phát đề) Đề thi gồm 4 câu trong 3 trang Họ và tên thí sinh:................................................................... Số báo danh:............................. Họ và tên, chữ ký: Giám thị thứ nhất:........................................................................................ Giám thị thứ hai:.......................................................................................... Yêu cầu: ++ 1. Chương trình được viết trên ngôn ngữ lập trình PASCAL hoặc C . 2. Các file chương trình và file dữ liệu được đặt tên chính xác như sau: Tên bài Tên chương trình Dữ liệu vào Dữ liệu ra Điểm Thời gian Câu 1 xau.* xau.inp xau.out 6,0 1s/Test Câu 2 mersen.* mersen.inp mersen.out 6,0 1s/Test Câu 3 daycon.* daycon.inp daycon.out 4,0 1s/Test Câu 4 vannghe.* vannghe.inp vannghe.out 4,0 1s/Test (Trong đó * là PAS nếu sử dụng Pascal hoặc CPP nếu sử dụng C++) Câu 1. (6,0 điểm) Xâu kí tự Cho một xâu kí tự S gồm N kí tự chữ cái thường. Yêu cầu: Hãy xác định kí tự xuất hiện nhiều lần nhất trong xâu S , nếu có nhiều kí tự cùng xuất hiện nhiều lần nhất thì in ra kí tự có thứ tự từ điển nhỏ hơn. Dữ liệu vào: File xau.inp chứa một xâu có N kí tự chữ cái thường (1 N 1000) . Dữ liệu ra: File xau.out có cấu trúc như sau: - Dòng 1: Ghi ra kí tự xuất hiện nhiều lần nhất, nếu có nhiều kí tự cùng xuất hiện nhiều lần nhất thì in ra kí tự có thứ tự từ điển nhỏ hơn. - Dòng 2: Ghi số lần xuất hiện tương ứng. Ví dụ: xau.inp xau.out Giải thích abbaac a Kí tự 'a' xuất hiện nhiều lần nhất với số lần xuất hiện 3 là 3 xau.inp xau.out Giải thích cbsvcccbfbb b Có 2 kí tự xuất hiện nhiều lần nhất là 'b' và 'c' với 4 cùng số lần xuất hiện là 4. In ra kí tự 'b' vì có thứ tự từ điển nhỏ hơn 'c' Ràng buộc: - 40% test với 1 N 10 . - 40% test với 10 N 100 . - 20% test với 100 N 1000 .
2. Câu 2. (6,0 điểm) Số Mersenne Một số nguyên tố được gọi là số Mersenne nếu nó có thể biểu diễn dưới dạng 2k 1 trong đó k cũng là số nguyên tố. Yêu cầu: Cho số tự nhiên n. Tìm số Mersenne lớn nhất nhưng nhỏ hơn n . Dữ liệu vào: File mersen.inp ghi số nguyên n (3 n 1010 ). Dữ liệu ra: File mersen.out ghi số Mersenne lớn nhất nhưng nhỏ hơn n tìm được. Ví dụ: mersen.inp mersen.out Giải thích 4 3 Ta có: 3 22 1 và 3, 2 đều là số nguyên tố. Do đó, 3 là số Mersenne lớn nhất và nhỏ hơn 4. mersen.inp mersen.out Giải thích 9 7 Ta có: 7 23 1 và 7, 3 đều là số nguyên tố. Do đó, 7 là số Mersenne lớn nhất và nhỏ hơn 9. Ràng buộc: - 40% test với 3<n 105. - 40% test với 105<n 109. - 20% test với 109<n 1010. Câu 3. (4,0 điểm) Dãy con Cho dãy số nguyên A gồm n số nguyên (a1, a2, , an). Một dãy con liên tiếp của A là một dãy gồm các phần tử liên tiếp nhau trong A. Yêu cầu: Hãy tìm dãy con liên tiếp có tổng các phần tử lớn nhất. Dữ liệu vào: File daycon.inp gồm 2 dòng: - Dòng đầu ghi số nguyên dương n (0<n 106). 6 - Dòng thứ hai ghi n số nguyên a 1, a2, , an (|ai| 10 , 1 i n), mỗi số cách nhau một khoảng trắng. Dữ liệu ra: File daycon.out gồm 2 dòng: - Dòng đầu ghi tổng lớn nhất tìm được. - Dòng thứ 2 ghi ra các phần tử của dãy con liên tiếp tìm được (giữ nguyên theo thứ tự ban đầu trong A). Mỗi phần tử cách nhau một khoảng trắng. Nếu có nhiều dãy như thế thì ghi ra dãy xuất hiện đầu tiên. Ví dụ: daycon.inp daycon.out Giải thích 6 5 Trong các dãy con liên tiếp thì dãy gồm các phần -2 3 -2 3 1 -2 3 -2 3 1 tử: 3 -2 3 1 có tổng bằng 5 là lớn nhất Ràng buộc: - 40% test với 0<n 102. - 40% test với 102<n 104. - 20% test với 104<n 106. 2
3. Câu 4. (4,0 điểm) Văn nghệ Trong một cuộc thi văn nghệ, có N thí sinh tham gia thi. Cuộc thi được tổ chức với nhiều vòng thi khác nhau. Mỗi vòng thi, thí sinh biểu diễn tốt nhất sẽ được N điểm, thí sinh tốt thứ nhì được N -1 điểm, thí sinh tốt thứ ba được N - 2 điểm, ... thí sinh xếp cuối cùng được 1 điểm. Điểm chung cuộc của từng thí sinh là tổng điểm của thí sinh đó đạt được qua các vòng thi. Thí sinh nào có điểm chung cuộc cao nhất sẽ giành giải nhất. Nếu có nhiều thí sinh cùng đạt điểm chung cuộc cao nhất thì tất cả họ đều giành được giải nhất. Hiện nay, chỉ còn một vòng thi nữa là cuộc thi kết thúc, tổng điểm của các thí sinh đạt được đến vòng thi này lần lượt là a1,a2 ,...,aN . Yêu cầu: Có bao nhiêu thí sinh có cơ hội giành được giải nhất chung cuộc? Dữ liệu vào: File vannghe.inp có cấu trúc như sau: - Dòng đầu tiên chứa số nguyên N (3 N 105 ) là số lượng thí sinh tham gia cuộc thi. 6 - N dòng tiếp theo, mỗi dòng ghi một số nguyên ai ( 0 ai 10 , 1 i N ) là số điểm của thí sinh thứ i trước vòng thi cuối cùng. Dữ liệu ra: File vannghe.out gồm 2 dòng: - Dòng 1: Ghi số lượng thí sinh có cơ hội giành được giải nhất chung cuộc. - Dòng 2: Ghi ra số thứ tự của các thí sinh có cơ hội giành được giải nhất chung cuộc theo thứ tự từ bé đến lớn, mỗi số cách nhau bởi một khoảng trắng. Ví dụ: vannghe.inp vannghe.out Giải thích 4 3 - Thí sinh thứ nhất có cơ hội giành được giải nhất nếu 9 1 2 4 vòng thi cuối cùng được 4 điểm; thí sinh thứ hai chỉ giành được 2 điểm; thí sinh thứ ba giành được 3 điểm 11 và thí sinh thứ tư giành được 1 điểm. Khi đó thí sinh 8 thứ nhất có điểm chung cuộc là 13 và giành giải nhất. 12 - Thí sinh thứ hai có cơ hội giành được giải nhất nếu đạt được 4 điểm ở vòng cuối cùng mà không cần quan tâm đến điểm ở vòng cuối của các thí sinh còn lại. - Thí sinh thứ ba không còn cơ hội giành được giải nhất. - Thí sinh thứ tư chỉ cần đạt được 3 hoặc 4 điểm ở vòng cuối là có cơ hội giành được giải nhất. Ràng buộc: - 40% test với 3 N 102. - 40% test với 102<N 103. - 20% test với 103<N 105. ------------- HẾT ------------- 3