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

1. SỞ GIÁO DỤC VÀ ĐÀO TẠO ĐỀ THI CHỌNHỌC SINH GIỎI LỚP 9 THCS CẤP TỈNH TỈNH NINH BÌNH NĂM HỌC 2021-2022 Môn: Tin học Ngày thi:23/02/2022 ĐỀ THI CHÍNH THỨC Thời gian làm bài:150phút (không kể thời gian phát đề) Đề thi gồm4 câu trong 2 trang Họ và tên thí sinh:................................................................... Số báo danh:............................. Họ và tên, chữ ký: Cán bộ coi thi thứ nhất :.............................................................................. Cán bộ coi thi thứ hai:................................................................................ Yêu cầu: Chương trình được viết trên ngôn ngữ lập trình PASCAL hoặc C++ Các file chương trình và file dữ liệu được đặt tên chính xác như sau: Tên Giới hạn Tên bài Dữ liệu vào Dữ liệu ra chương trình thời gian, dữ liệu Câu 1 cpdx.* cpdx.inp cpdx.out 1s, 1024mb/test Câu 2 xauhn.* xauhn.inp xauhn.out 1s, 1024mb/test Câu 3 dem.* dem.inp dem.out 1s, 1024mb/test Câu 4 sum.* sum.inp sum.out 1s, 1024mb/test (trong đó * là PAS nếu sử dụng Pascal hoặc CPP nếu sử dụng C++ Câu 1. CHÍNH PHƯƠNG ĐỐI XỨNG (6,0 điểm) Số tự nhiên N là số chính phương đối xứng nếu số đó là số chính phương đồng thời khi đọc các chữ số của số đó từ trái sang phải hay đọc từ phải sang trái đều có kết quả như nhau. Yêu cầu: Cho số nguyên dương N. Tìm số chính phương đối xứng lớn nhất nhỏ hơn N. Dữ liệu vào: Trong tệp cpdx.inpchứa số nguyên dương N. Dữ liệu ra: Trong tệp cpdx.out ghi số nguyên dương K là số tìm được. Ví dụ: cpdx.inp cpdx.out 150 121 Giới hạn dữ liệu:N<1010. Trong bộ test có:40% test vớiN<103; 40% test với N<106. Câu 2. XÂU HẠT NHÂN (5,0 điểm) Xâu P được gọi là xâu hạt nhân của xâu Snếu P là xâu ngắn nhất mà khi ghép xâu P một số lần thì được xâu S (có thể chỉ cần ghép 1 lần) Yêu cầu: Cho xâu S có độ dài k. Hãy tìm xâu hạt nhân P. Dữ liệu vào: Trong tệp xauhn.inp chứa xâu S. Dữ liệu ra: Trong tệp xauhn.outghi xâu P tìm được. Ví dụ: xauhn.inp xauhn.out xauhn.inp xauhn.out ab ab abcabcabc abc Giới hạn dữ liệu:1 k 105. Trong bộ test có: 60% test với k<255;
2. 2 Câu3. ĐẾM HÌNH VUÔNG(5,0 điểm) Cho một lưới ô vuông kích thước NxN. Trên ô (i,j) của lưới người ta viết số nguyên không âm aij. Ta gọi hình vuông đồng nhất bậc 2 của lưới là tập gồm 4 ô nằm trên giao của hai dòng liên tiếp và 2 cột liên tiếp của lưới với các số viết trên chúng là giống nhau. Hai hình vuông đồng nhất bậc 2 được gọi là cùng loại nếu các số ghi trong hai hình vuông đó như nhau. Yêu cầu: Cho số nguyên dương N. Đếm số lượng hình vuông đồng nhất bậc 2 của cùng một loại xuất hiện nhiều nhấttrong bảng lưới ô vuông. Dữ liệu vào: Trong tệp dem.inpchứa các thông tin sau: + Dòng đầu tiên chứa số nguyên dương N + Dòng thứ i trong số N dòng tiếp theo chứa các số ai1, ai2, ..., aiN( với i = 1, 2, ..., N), hai số liên tiếp trên một dòng được viết cách nhau một dấu cách. Dữ liệu ra:Trong tệp dem.outghi số lượng hình vuông đồng nhất bậc 2 xuất hiện nhiều nhất của cùng một loại. Ví dụ: dem.inp dem.out dem.inp dem.out dem.inp dem.out 3 2 6 7 6 3 001 1 1 1 1 1 1 0 1 1 0 2 2 1 1 1 1 1 1 1 0 0 0 1 1 1 2 2 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 8 8 1 1 0 0 0 0 0 0 1 1 8 8 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 3 3 Giới hạn dữ liệu: 2≤N≤10 ; aij ≤10 . Trong bộ test có: 40% test chỉ có 1 loại hình vuông đồng nhất bậc 2; 40% test trong lưới ô vuông chỉ có số 0 và số 1. Câu 4. TÍNH TỔNG(4,0 điểm) Trên một màn hình lớn, người ta lần lượt cho xuất hiện các số của một dãy gồm Nsố nguyên không âm a1, a2, , aN và cứ lặp đi lặp lại như thế (nghĩa là sau khi a i xuất hiện vài giây đến lượt ai+1 xuất hiện, số xuất hiện sau aN là a1). Yêu cầu:Hãy tính tổng của Ksố xuất hiện liên tiếp trên màn hình bắt đầu từ lần thứ xuất hiện thứ M. Dữ liệu vào:Trong tệp sum.inpchứa các thông tin sau: + Dòng đầu tiên gồm ba số nguyên N, K,M. + Trong N dòng sau, dòng thứ i chứa số ai. Dữ liệu ra:Trong tệpsum.outghi giá trị tổng tìm được. Ví dụ: sum.inp sum.out sum.inp sum.out 3 21 5 3 7 5 25 2 2 3 3 6 6 3 9 6 Giới hạn dữ liệu:N<10 ;K<10 ; ai <10 . Trong bộ test có:40% test có M+K≤N 40% test có M+K<106 ----------------------------- HẾT-----------------------------