Đề thi học sinh giỏi cấp Thành phố môn Tin học Lớp 9 - Năm học 2013-2014 - 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 2013 - 2014 ĐỀ CHÍNH THỨC Môn thi: Tin học Ngày thi: 31/03/2014 Thời gian làm bài 150 phút (Đề thi gồm 02 trang) Câu 1. Hiệu hai phân số ( 6 điểm): Tên file chương trình: CAU1.PAS Cho bốn số nguyên dương a, b, c, d, mỗi số không vượt quá 105. Yêu cầu: Tìm hai số nguyên x, y để phân số x/y tối giản và bằng hiệu của hai phân số a/b – c/d, trong đó y>0. Dữ liệu: vào từ tệp văn bản CAU1.INP - Dòng đầu chứa hai số a, b. - Dòng thứ hai chứa hai số c, d. Kết quả: ghi ra tệp văn bản CAU1.OUT hai số x, y trên cùng một dòng, cách nhau một dấu cách. Ví dụ: CAU1.INP CAU1.OUT Giải thích 1 6 -1 4 1/6 – 5/12 = -1/4 5 12 Câu 2: Đua robot (6 điểm) Tên file chương trình: CAU2.PAS Trong cuộc đua tốc độ có n robot tham gia được đánh số từ 1 đến n. Đường đua có độ dài d (mét). Robot thứ i (1 <= i <= n) có vận tốc đua không đổi là vi (mét/phút). Các robot xuất phát theo thứ tự từ 1 đến n và cách nhau 1 phút. Robot i gọi là vượt robot j (1 <= j <= n) nếu i xuất phát sau j và về đích trước j. Yêu cầu: Xác định số lượt vượt nhau của tất cả các robot trong cuộc đua. Dữ liệu: Vào từ file văn bản CAU2.INP: - Dòng đầu chứa hai số nguyên dương n và d (n < 103, d < 109). - Dòng tiếp theo chứa n số nguyên dương vi (1 <= i < n), mỗi số không vượt quá 1000. Kết quả: Ghi ra tệp văn bản CAU2.OUT số lượt vượt nhau của tất cả các robot trong cuộc đua. Ví dụ: CAU2.INP CAU2.OUT Giải thích 5 10 7 Robot 2 vượt robot 1; Robot 3 vượt các robot 1, 2; Robot 4 1 2 4 3 8 vượt robot 1;Robot 5 vượt các robot 1, 2, 4. Tổng số lần vựt là 7. Câu 3: Tìm kiếm trong xâu (4 điểm) : Tên file chương trình: CAU3.PAS Cho xâu S có độ dài tối đa 250 kí tự, gồm chữ cái in hoa, in thường và chữ số. Yêu cầu: Đếm xem trong S có bao nhiêu kí tự khác nhau và tìm độ dài đoạn kí tự liên tiếp dài nhất trong xâu S tạo thành xâu X đối xứng. Xâu kí tự X được gọi là đối xứng nếu đọc từ trái sang phải hoặc ngược lại đều thu được xâu như nhau. Dữ liệu: Vào từ tệp văn bản CAU3.INP một dòng duy nhất chứa xâu S. Kết quả: Ghi ra tệp văn bản CAU3.OUT: - Dòng thứ nhất ghi số kí tự khác nhau trong S. - Dòng thứ hai ghi độ dài xâu X tìm được. Ví dụ: CAU3.INP CAU3.OUT Giải thích AbcabA12321ABCbca 9 Các kí tự khác nhau gồm: A,B,C,a,b,c,1,2,3. 7 Xâu X tìm được là A12321A Câu 4: Trồng cây (4 điểm) : Tên file chương trình: CAU4.PAS Dọc theo một tuyến phố thẳng có n vị trí kế tiếp nhau để trồng cây đánh số từ 1 đến n. Hiện tại chỉ có vị trí thứ k (1 <= k <= n) đã trồng một cây có độ cao là ak, còn các vị trí khác để trống. Theo dự kiến, người ta sẽ trồng cây có độ cao ai tại vị trí thứ i (1 <= i <= n, i ≠ k). Tuy nhiên, để tăng vẻ đẹp cho hàng cậy, người ta muốn tìm một phương án sắp xếp các cây cần trồng vào các vị trí thích hợp (trừ vị trí thứ k) sao cho tổng tất cả các độ chênh lệch của hai cây trồng liền kề nhau là nhỏ nhất. Độ chênh lệch của hai cây được trồng tại hai vị trí liền nhau là giá trị tuyệt đối của hiệu độ cao của hai cây. Yêu cầu: Tìm giá trị nhỏ nhất t của tổng tất cả các độ chênh lệch của hai cây trồng liền nhau.. 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 n và k (n <= 103, 1 <= k <= n). - Dòng sau chứa n số nguyên dương ai (1 <= i <= n), là độ cao của cây thứ i theo dự kiến. Mỗi số không vượt quá 106. Kết quả: Ghi ra tệp văn bản CAU4.OUT số t tìm được. Ví dụ: CAU4.INP CAU4.OUT Giải thích 5 2 5 Vị trí 1 trồng cây có độ cao 2, vị trí 3 trồng cây 7 3 4 2 6 có độ cao 4, vị trí 4 trồng cây có độ cao 6, vị trí 5 trồng cây có độ cao 7. Tổng độ chênh lệch nhỏ nhất là 5. ------------------ Hết -------------------