Đề thi học sinh giỏi cấp Thành phố môn Tin học Lớp 9 - Năm học 2015-2016 - Sở GD&ĐT Hà Nội (Có đáp án)

SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI HỌC SINH GIỎI LỚP 9 CẤP THÀNH PHỐ HÀ NỘI Năm học 2015 – 2016 ĐỀ CHÍNH THỨC Môn thi: TIN HỌC Ngày thi: 14/4/2016 Thời gian làm bài: 150 phút (Đề thi gồm 02 trang) Câu 1. Tích lấy dư ( 6 điểm): Tên tệp chương trình: CAU1.* Cho ba số nguyên dương a, b, c. Yêu cầu: Tìm số dư của phép chia tích các số nguyên trong đoạn [a, b] cho số c. Dữ liệu: Vào từ tệp văn bản CAU1.INP chứa ba số a, b, c (1 ≤ a < b ≤ 104, 1 < c ≤ 109). Kết quả: Ghi ra tệp văn bản CAU1.OUT số dư tìm được. Ví dụ: CAU1.INP CAU1.OUT Giải thích 5 10 11 5 Ta có: 5*6*7*8*9*10 mod 11 = 5 Câu 2: Điểm thưởng (5 điểm) Tên file chương trình: CAU2.* Trong cuộc thi tin học trẻ, mỗi thí sinh phải trả lời n câu hỏi. Để tăng tính hấp dẫn của cuộc thi, ba tổ chức quyết định đưa ra n số điểm thưởng a1, a2, , an. Theo thể lệ cuộc thi, thí sinh trả lời đúng k câu hỏi (1 ≤ k ≤ n) sẽ nhận được số điểm thưởng bằng số lớn nhất trong các số a1, a2, , ak. Yêu cầu: Xác định số điểm thưởng của thí sinh tương ứng với mỗi giá trị k từ 1 đến n. Dữ liệu: Vào từ tệp văn bản CAU2.INP: - Dòng đầu chứa hai số nguyên dương n không vượt quá 30000; 3 - Dòng thứ hai chứa n số nguyên dương a1, a2, , an, mỗi số không vượt quá 10 . Kết quả: Ghi ra tệp văn bản CAU2.OUT một dòng gồm n số là điểm thưởng cho thí sinh trả lời đúng lần lượt 1, 2, , n câu hỏi. Ví dụ: CAU2.INP CAU2.OUT Giải thích 3 6 6 7 Thí sinh trả lời đúng 1 câu sẽ nhận điểm thưởng là 6; trả lời 6 1 7 đúng 2 câu sẽ nhận điểm thưởng là 6, trả lời đúng 3 câu sẽ nhận điểm thưởng là 7. Câu 3: Tìm xâu (5 điểm) : Tên file chương trình: CAU3.* Cho trước xâu ký tự s độ dài n chỉ chứa các chữ cái tiếng Anh. Bắt đầu từ xâu s, thực hiện phép hoán vị vòng quanh các ký tự sẽ nhận được một dãy gồm m xâu khác nhau (m ≤ n). Sau khi sắp xếp m xâu trong dãy nhận được theo thứ tự từ điển, xâu ký tự s ban đầu có vị trí thứ k. Ví dụ: Với s = ‘BCA’ khi hoán vị vòng quanh nhận được 3 xâu khác nhau ‘BCA’, ‘CAB’, ‘ABC’. Sắp xếp theo thứ tự từ điển có dãy các xâu lần lượt là ‘ABC’, ‘BCA’, ‘CAB’; xâu s ban đầu đứng ở vị trí thứ k = 2. Yêu cầu: Cho biết xâu x là một trong m xâu nhận được từ s bằng cách hoán vị vòng quang các ký tự và vị trí k của xâu s. Xác định xâu s. Dữ liệu: Vào từ tệp văn bản CAU3.INP: - Dòng đầu chứa số nguyên dương k; - Dòng thứ hai chứa xâu x có độ dài n (k ≤ n ≤ 100). Kết quả: Ghi ra tệp văn bản CAU3.OUT xâu s tìm được. Trong trường hợp không xác định được s thì ghi số -1. Ví dụ: CAU3.INP CAU3.OUT Giải thích 2 BCA Từ xâu ‘BCA’ bằng cách hoán vị vòng quanh ABC các ký tự sẽ xuất hiện xâu ‘ABC’ và xâu s có số thứ tự k = 2 khi sắp xếp các xâu nhận được theo thứ tự từ điển. Câu 4: Di chuyển cây (4 điểm) : Tên file chương trình: CAU4.* Thành phố ZXY có một vườn bách thảo được mô tả dưới dạng bản đồ hình chữ nhật gồm m dòng và và n cột. Trong vườn có k loại cây khác nhau, đánh số từ 1 đến k (k ≤ 100). Mỗi ô của bản đồ chứa duy nhất số nguyên dương i (i ≤ k) nếu tại ô này có trồng cây loại i, hoặc số 0 nếu ô này không có cây. Chính quyền thành phố muốn chỉnh trang khu vườn cho đẹp hơn bằng cách giữ lại những hàng cây có ít nhất t cây liền nhau, thuộc cùng một loại cây, nằm trên cùng một dòng hoặc cùng một cột. Những cây không thuộc hàng cây nào đó sẽ được di chuyển đến vị trí khác phù hợp hơn. Yêu cầu: Cho trước bản đồ vườn cây như trên, hãy đếm số lượng cây cần phải di chuyển. Dữ liệu: Vào từ tệp văn bản CAU4.INP: - Dòng đầu chứa ba số nguyên dương m, n, và t (1 < m, n, t ≤ 100). - Trong m dòng tiếp theo, mỗi dòng chứa n số tự nhiên mô tả bản đồ vườn bách thảo. Kết quả: Ghi ra tệp văn bản CAU4.OUT số lượng cây cần phải di chuyển. Ví dụ: CAU4.INP CAU4.OUT Giải thích 5 6 3 10 Những số gạch chân dưới đây biểu thị những 1 3 3 3 3 4 cây cần phải di chuyển: 1 2 3 2 0 4 1 3 3 3 3 4 3 2 2 2 4 4 1 2 3 2 0 4 1 0 0 2 4 0 3 2 2 2 4 4 1 2 3 0 4 4 1 0 0 2 4 0 1 2 3 0 4 4 ------------------ Hết ------------------- Chú ý: - Cán bộ coi thi không giải thích gì thêm; - Các tệp dữ liệu vào là đúng đắn không cần kiểm tra; - Làm bài với các tên tệp đúng như quy định trong đề, trong đó dấu “*” là phần mở rộng mặc định theo ngôn ngữ lập trình mà thí sinh sử dụng (Ví dụ: CAU1.PAS, CAU1.CPP, ). Họ và tên thí sinh: . Số báo danh: Chữ ký giám thị 1 Chữ ký giám thị 2