Đề thi HSG Tin 9 tỉnh Long An năm 2014-2015

SỞ GIÁO DỤC VÀ ĐÀO TẠO LONG AN ĐỀ CHÍNH THỨC KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH LỚP 9. MÔN THI : TIN HỌC NGÀY THI : 17/4/2015 THỜI GIAN : 150 PHÚT (không kể thời gian phát đề) Lưu ý: Thí sinh tạo thư mục là SBD của mình, làm bài và lưu với tên tập tin là bai1.pas, bai2.pas, bai3.pas vào thư mục SBD vừa tạo. Bài 1: (7.0 điểm) Số đối xứng là số có thể viết từ trái sang phải hay viết từ phải sang trái các chữ số của nó ta vẫn được chính nó, ví dụ các số 363, 1221, 474 là số đối xứng. Có một số x ta lấy các chữ số từ phải qua trái của nó viết lại theo thứ tự từ trái qua phải ta thu được một số mới k, số k gọi là số đảo của số x. Ví dụ x=123 thì k=321; x=130 thì k=031 (giá trị thực của k=31 vì số 0 đầu không có nghĩa). Cho một số nguyên dương n, qua phép biến đổi sau đây ta luôn thu được một số đối xứng: Lấy số n cộng với số đảo của nó thu được tổng là n 1, nếu n1 chưa là số đối xứng thì tiếp tục lấy n1 cộng với số đảo của n1 thu được tổng n2 và tiếp tục làm như vậy đến khi nhận được số đối xứng. Yêu cầu: Viết chương trình nhập số nguyên dương n ( 10< N ≤ 65000). Xuất ra màn hình số đối xứng thu được qua phép biến đổi trên và số lần biến đổi để thu được số đối xứng. Ví dụ: Nhập n 157 Kết quả trên màn hình So doi xung = 8888 So lan bien doi = 3 Giải thích 157+751=908 (biến đổi lần 1) 908+809=1717 (biến đổi lần 2) 1717+7171=8888 (biến đổi lần 3 thu được số đối xứng) Bài 2: (7.0 điểm) Từ địa điểm A đến địa điểm B có một số con đường đi, trên mỗi đường đi tốn một chi phí riêng, chi phí là một số nguyên từ 1 đến 9. Tương tự từ B đến C, từ C đến D, … cũng vậy, xem hình minh họa sau: 2 1 A Điểm đầu 4 B 3 2 1 7 2 D C 4 3 7 5 E .... Điểm cuối 6 Yêu cầu: Viết chương trình cho biết có bao nhiêu cách đi từ điểm đầu tiên đến điểm cuối cùng (đường đi phải qua tất cả các điểm) và đi theo đường nào để tốn chi phí thấp nhất. - Dữ liệu vào: Nhập từ bàn phím một dòng văn bản cho biết các địa điểm và các số cho biết chi phí tương ứng trên các đường đi giữa hai điểm đó. Ví dụ: A2143B213C74D2756E nghĩa là có 5 địa điểm A,B,C,D,E và điểm cuối là E. Giữa A và B có 4 con số 2143 tương ứng chi phí của 4 đường đi từ A đến B. Tương tự giữa các điểm B và C, C và D, D và E. - Dữ liệu ra: Xuất ra màn hình gồm hai dòng, dòng đầu là một số nguyên cho biết số cách có thể đi từ điểm đầu đến điểm cuối mà phải qua tất cả các điểm. Dòng thứ 2 là một chuỗi cho biết đường đi từ điểm đầu đến điểm cuối cùng với chi phí thấp nhất giữa các điểm. Trang 1/2 Ví dụ: Chuỗi nhập vào A2143B213C74D2756E Xuất ra màn hình 96 A1B1C4D2E Giải thích A qua B có 4 cách, B qua C có 3 cách, C qua D có 2 cách, D qua E có 4 cách => có 4*3*2*4=96 cách đi từ A đến E. Từ A qua B có chi phí thấp nhất là 1 Từ B qua C có chi phí thấp nhất là 1 Từ C qua D có chi phí thấp nhất là 4 Từ D qua E có chi phí thấp nhất là 2 Bài 3: (6.0 điểm) Bộ ba số nguyên dương a, b, c được gọi là bộ ba Pytago khi bình phương của một trong ba số bằng tổng bình phương của hai số còn lại. Ví dụ a=3, b=5, c=4 là bộ ba Pytago vì 52=32+42. Yêu cầu: Viết chương trình đọc 4 số nguyên dương a,b,c và n từ tập tin bai3.inp (với 0