Đề thi HSG Tin 9 tỉnh Bình Định năm 2015-2016

SỞ GIÁO DỤC ĐÀO TẠO BÌNH ĐỊNH ĐỀ CHÍNH THỨC KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH LỚP 9 THCS KHÓA NGÀY: 18-3-2015 Môn thi: TIN HỌC Thời gian: 150 phút (không kể thời gian phát đề) Ngày thi: 18/3/2015 Tổng quan bài thi: Bài Tên bài Tên tệp chương trình 1 Liên phân số LIENPS.PAS 2 3 Số nguyên tố cùng nhau Tìm đường hái quả NTCN.PAS HAIQUA.PAS Tên tệp dữ liệu vào Nhập từ bàn phím NTCN.INP HAIQUA.INP Tên tệp dữ liệu ra Xuất trên màn hình NTCN.OUT HAIQUA.OUT Bài 1: Liên phân số (7,0 điểm): Số hữu tỉ dương a/b luôn được biểu diễn dưới dạng một liên phân số hữu hạn: Liên phân số này ký hiệu là [q 0,q1,q2,...,qn], trong đó q00; q1,q2,...,qn là những số nguyên dương; qn>1; n gọi là độ dài của liên phân số. Hãy viết chương trình biến đổi một phân số a/b thành liên phân số hữu hạn. Dữ liệu vào là hai số nguyên dương a, b nhập từ bàn phím để biểu diễn phân số a/b. Dữ liệu ra là một dòng gồm các số q0,q1,q2,...,qn biểu diễn dạng liên phân số của phân số a/b. Các số viết cách nhau ít nhất một khoảng cách. Ví dụ: Input Output a=7 122 b=5 Bài 2: Số nguyên tố cùng nhau: (7,0 điểm): Hai số nguyên dương được gọi là nguyên tố cùng nhau nếu ước số chung lớn nhất của chúng bằng 1. Cho N số nguyên dương A1,A2,...,AN. Gọi M là giá trị lớn nhất trong các số A1,A2,...,AN. Viết chương trình tìm số nguyên dương X lớn nhất không vượt quá M mà X nguyên tố cùng nhau với tất cả các số A1,A2,...,AN. Dữ liệu vào là tệp NTCN.Inp có cấu trúc như sau: - Dòng đầu là số nguyên dương N (N100). - N dòng tiếp theo, mỗi dòng chứa một giá trị tương ứng A1,A2,...,AN (Ai1000;i=1,2,...,N). Dữ liệu ra là tệp NTCN.Out chứa số nguyên X tìm được thỏa mãn điều kiện của bài toán. Ví dụ: NTCN.Inp NTCN.Out 3 13 4 12 15 Bài 3: Tìm đường hái quả (6,0 điểm): Một khu vườn hình chữ nhật kích thước MxN được chia thành các ô vuông đơn vị để trồng một loại cây ăn quả. Trên mỗi ô thì số quả tương ứng có thể hái được là A[i,j] (1iM; 1jN). Một người khách dạo qua vườn và hái tất cả các quả trên những ô đi qua. Vị trí xuất phát từ ô [1,1] và kết thúc tại ô [M,N] với hành trình là sang ô chung cạnh theo hướng tăng của i hoặc j (sang phải hoặc đi xuống – như hình vẽ). Hãy viết chương trình tìm lộ trình đi của người đó để hái được nhiều quả nhất. 1 3 5 7 2 7 9 4 2 2 2 3 1 6 7 7 4 6 2 5 Dữ liệu vào là tệp HAIQUA.INP có cấu trúc như sau: - Dòng đầu tiên là hai số M, N nguyên dương cách nhau một khoảng cách (0