Đề thi học sinh giỏi cấp Thành phố môn Tin học Lớp 9 - Năm học 2014-2015 - 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 THÀNH PHỐ - LỚP 9 HÀ NỘI Năm học 2014 - 2015 ĐỀ CHÍNH THỨC Môn thi: TIN HỌC Ngày thi: 09/04/2015 Thời gian làm bài 150 phút (Đề thi gồm 02 trang) Câu 1. Phương trình ( 6 điểm): Tên tệp chương trình: CAU1.PAS Cho phương trình ax + by = c với a, b, c là các số nguyên dương. Yêu cầu: Tìm số lượng cặp (x, y), với x, y nguyên dương, là nghiệm của phương trình. Dữ liệu: Vào từ tệp văn bản CAU1.INP một dòng duy nhất chứa ba số nguyên dương a, b, c, mỗi số không vượt quá 109. Kết quả: Ghi ra tệp văn bản CAU1.OUT số lượng các cặp nghiệm nguyên dương (x, y) của phương trình. Ví dụ: CAU1.INP CAU1.OUT Giải thích 2 4 20 4 Các cặp nghiệm nguyên dương của phương trình 2x + 4y = 20 là: (2,4), (4,3), (6,2), (8,1). Câu 2: Chia nhóm (6 điểm) Tên file chương trình: CAU2.PAS Cho n số nguyên a1, a2, , an. Người ta muốn chia n số nguyên này thành các nhóm, trong mỗi nhóm hiệu của số lớn nhất và số nhỏ nhất không vượt quá số nguyên dương h cho trước. Yêu cầu: Xác định số lượng nhóm ít nhất khi chia nhóm n số nguyên đã cho thỏa mãn điều kiện trê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 và h (n < 103, h < 109). - Trong n dòng tiếp theo, dòng thứ i (1 <= i <= n) chứa số nguyên ai có giá trị tuyệt đối không vượt quá 109. Kết quả: Ghi ra tệp văn bản CAU2.OUT số lượng nhóm ít nhất tìm được. Ví dụ: CAU2.INP CAU2.OUT Giải thích 6 3 2 Có thể chia 6 số đã cho thành hai nhóm. Nhóm thứ nhất gồm các -7 số thứ 1, thứ 3 và thứ 6 và nhóm thứ hai là các số còn lại. Hai 27 nhóm này đều có hiệu của số lớn nhất và số nhỏ nhất là 2 nhỏ -5 hơn 3. 26 28 -6 Câu 3: Tạo số (5 điểm) : Tên file chương trình: CAU3.PAS Cho trước số nguyên dương t. Người ta tạo một số nguyên dương x bằng cách sau: Trước hết, biểu diễn số t = p1.p2..pk trong đó pi (1 <= i <= k) là các số nguyên tố (k có thể bằng 1); tiếp theo viết các số p1, p2, , pk theo một thứ tự nào đó liên tiếp nhau để nhận được số nguyên dương x. Yêu cầu: Tìm giá trị lớn nhất của x. Dữ liệu: Vào từ tệp văn bản CAU3.INP chứa số nguyên dương t không vượt quá 109. Kết quả: Ghi ra tệp văn bản CAU3.OUT giá trị x lớn nhất tìm được. Ví dụ: CAU3.INP CAU3.OUT Giải thích 476 72217 Có 476 = 2.2.7.17 nên số x lớn nhất là 72217 Câu 4: Bảng số (4 điểm) : Tên file chương trình: CAU4.PAS Cho trước bảng số A gồm m hàng, n cột. Mỗi ô trong bảng số chứa một số nguyên dương, gọi là giá trị của ô. Tất cả các ô (ít nhất là 2 ô) có cùng giá trị, kề cạnh hoặc kề đỉnh, tạo thành một vùng số. Số lượng ô trong một vùng số gọi là diện tích của vùng số đó. Yêu cầu: Tính số lượng vùng số có trong bảng A và tính diện tích của vùng số lớn nhất. Dữ liệu: Vào từ tệp văn bản CAU4.INP: - Dòng đầu chứa hai số nguyên dương m, n, mỗi số không vượt quá 100. - Trong m dòng tiếp theo, mỗi dòng chứa n số nguyên dương, mỗi số không vượt quá 100. Kết quả: Ghi ra tệp văn bản CAU4.OUT: - Dòng đầu ghi số lượng các vùng số có trong bảng A. - Dòng thứ hai ghi diện tích của vùng số lớn nhất. Ví dụ: CAU4.INP CAU4.OUT Giải thích 5 6 8 Có 8 vùng số gồm: 2 vùng số 1; 1 vùng số 2; 2 vùng 1 2 1 4 5 4 5 số 3; 2 vùng số 4; 1 vùng số 5. Trong 8 vùng số trên, 1 3 1 4 5 4 diện tích vùng số lớn nhất là 5. 3 1 2 3 3 4 2 2 4 5 3 3 2 2 3 2 1 1 ------------------ 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 đề. Họ và tên thí sinh: Số báo danh: