Đề thi HSG Tỉnh Tin học 9 - Đề số 1

ĐỀ THI HỌC SINH GIỎI TỈNH ĐỀ SỐ 1 MÔN: TIN HỌC 9 Thời gian: 150 phút Bài 1: (7 điểm) Đồng hồ Trên mặt đồng hồ, kim ngắn đang chỉ vào số 1. Có hai thao tác trên đồng hồ gồm: Thao tác vặn kim đồng hồ qua chiều thuận n số được ký hiệu là: +n và thao tác vặn kim theo chiều ngược lại n số được ký hiệu là: –n. Hãy tìm giá trị số mà kim ngắn chỉ định sau khi thực hiện một thao tác. Ví dụ: +3 nghĩa là vặn kim ngắn từ số 1 đến số 4 theo chiều thuận. –4 nghĩa là vặn kim ngắn từ số 1 đến số 9 theo chiều ngược. Dữ liệu vào: Cho file DONGHO.INP với một dòng duy nhất ghi thao tác vặn. Kết quả: Ghi ra file DONGHO.OUT một số nguyên là giá trị kim ngắn chỉ định. DONGHO.INP DONGHO.OUT +3 4 hoặc DONGHO.INP DONGHO.OUT -4 9 Ràng buộc dữ liệu: n < 1000000. Page 1 Bài 2: (7 điểm) Tìm số Cho một dãy n số nguyên a1, a2, ..., an. Hãy tìm giá trị lớn nhì trong dãy. Ví dụ: Cho dãy số gồm 3 phần tử: 1, 2, -3 Giá trị lớn nhì là: 1 Dữ liệu vào: Cho file TIMSO.INP gồm: - Dòng đầu tiên chứa số n là số lượng các phần tử của dãy a. - n dòng tiếp theo, dòng thứ i chứa một số nguyên ai. Kết quả: Ghi ra file TIMSO.OUT một số nguyên là giá trị lớn nhì. Trong trường hợp không tìm thấy thì ghi ra file là: No solution TIMSO.INP TIMSO.OUT 3 1 1 2 -3 Ràng buộc dữ liệu: n < 10000; -32000 < ai < 32000. Bài 3: (6 điểm) Chia kẹo Cho n túi kẹo, túi thứ i có ai viên. Hãy chia các túi này thành hai phần sao cho số viên kẹo chênh lệch giữa hai phần là nhỏ nhất. Ví dụ: Cho 7 túi có số viên kẹo trong từng túi lần lượt là: 30, 25, 40, 20, 26, 30, 20. Page 2 Sau khi chia thành 2 phần để có số viên kẹo chênh lệch giữa 2 phần nhỏ nhất ta được kết quả: Phần thứ nhất: 30 + 25 + 40 = 95 Phần thứ hai: 20 + 26 + 30 + 20 = 96 Vậy số viên chênh lệch nhỏ nhất là: 96 – 95 = 1 Dữ liệu vào: Cho file CHIAKEO.INP gồm: - Dòng đầu tiên chứa số n là số lượng các túi kẹo. - n dòng tiếp theo, dòng thứ i chứa số viên của túi kẹo thứ i. Kết quả: Ghi ra file CHIAKEO.OUT một số nguyên là số viên chênh lệch nhỏ nhất. CHIAKEO.INP CHIAKEO.OUT 7 1 30 25 40 20 26 30 20 Ràng buộc dữ liệu: n < 100000; 0 < ai < 50000. Page 3 Page 4