Kỳ thi học sinh giỏi lớp 12 THPT cấp thành phố môn Tin học

SỞ GIÁO DỤC-ĐÀO TẠO KỲ THI HỌC SINH GIỎI LỚP 12-THPT CẤP THÀNH PHỐ TP HỒ CHÍ MINH Năm học : 2006 – 2007 Khóa ngày: 07/12/2006 Môn thi : TIN HỌC Thời gian làm bài: 180 phút Tổng quan về đề thi: Tên bài Tên chương trình File dữ liệu vào File kết quả Bài 1 Dãy con DAYCON.PAS DAYCON.INP DAYCON.OUT Bài 2 Biểu diễn BIEUDIEN.PAS BIEUDIEN.INP BIEUDIEN.OUT Bài 3 Sắp xếp mã XEPMA.PAS XEPMA.INP XEPMA.OUT Bài 1: DÃY CON (10 điểm) Bài toán: Cho một dãy số gồm N số nguyên (1 ≤ N ≤ 3000) có giá trị trong [-1000, 1000]. Tìm dãy số liên tiếp dài nhất của dãy ban đầu mà tổng của chúng có trị tuyệt đối nhỏ nhất. Dữ liệu: Cho trong file văn bản DAYCON.INP, trong đó: • Dòng đầu là số nguyên N • Trên dòng i (2 ≤ i ≤ N+1) là số hạng thứ i-1 của dãy số ban đầu. Kết quả: Cho trong file văn bản DAYCON.OUT, gồm một dòng duy nhất chứa ba số nguyên, trong đó: • Chỉ số của số đầu tiên của dãy tìm được • Chỉ số của số cuối cùng của dãy tìm được • Trị tuyệt đối của tổng các số hạng của dãy tìm được. Lưu ý: Nếu có nhiều dãy con có trị tuyệt đối của tổng các số hạng là nhỏ nhất và số số hạng là lớn nhất, chỉ xuất ra dãy con có chỉ số của số đầu tiên là nhỏ nhất. Ví dụ: DAYCON.INP DAYCON.OUT 6 5 10 -5 -6 2 4 4 6 0 trang 1/3 ĐỀ CHÍNH THỨC (gồm có 3 trang) Bài 2: BIỂU DIỄN (5 điểm) Mỗi số nguyên dương N có thể biểu diễn bằng tổng các số hạng dạng (2a)(3b) sao cho mỗi số hạng của tổng không chia hết cho bất kỳ số hạng nào khác của tổng. Mỗi biểu diễn như vậy gọi là một biểu diễn 2_3 của số N. Ví dụ: Chú ý rằng có hai biểu diễn 2_3 của số 31. Bài toán: Tìm số số hạng trong biểu diễn 2_3 của số nguyên dương N cho trước. Nếu có nhiều biểu diễn, chỉ xuất ra số số hạng của biểu diễn có số số hạng lớn nhất. Ví dụ, 31 có hai cách biểu diễn, nhưng chỉ xuất ra số 3. Dữ liệu: Cho trong file văn bản BIEUDIEN.INP, gồm: • Dòng đầu là số nguyên dương C (1 ≤ C ≤ 1000) chỉ số bộ dữ liệu. • Mỗi bộ dữ liệu gồm 1 dòng duy nhất, trên đó có duy nhất 1 số nguyên dương N (1 ≤ N < 231). Kết quả: Cho trong file văn bản BIEUDIEN.OUT, trên dòng i (1 ≤ i ≤ C) chứa số nguyên dương là số số hạng của biểu diễn 2_3 của số nguyên dương N cho trong dòng i+1 của file BIEUDIEN.INP. Ví dụ: BIEUDIEN.INP BIEUDIEN.OUT 4 1 7 16 31 1 2 1 3 trang 2/3 Bài 3: XẾP MÃ (5 điểm) Bài toán: Cho một bàn cờ vua kích thước n*n. Trên bàn cờ có một số ô bị hư. Tìm số quân mã nhiều nhất có thể đặt trên bàn cờ tại những ô chưa bị hư sao cho không có quân mã nào ăn nhau. Hình bên: Quân mã đặt tại ô S có thể ăn các quân khác đặt tại các ô đánh dấu X. Dữ liệu: Cho trong file văn bản XEPMA.INP, trong đó: • Trên dòng đầu tiên ghi 2 số nguyên n và m cách nhau bởi một khoảng trắng. Trong đó 1 ≤ n ≤ 200 và 0 ≤ m <n2 ; n là kích thước bàn cờ và m là số ô bị hư. • Trên mỗi dòng trong m dòng tiếp theo ghi 2 số nguyên x và y cách nhau bởi khoảng trắng ( 1 ≤ x, y ≤ n ); x và y là toạ độ của các ô bị hư. Toạ độ của ô góc trái trên của bàn cờ là (1, 1) và của ô góc phải dưới là (n, n). Các ô bị hư không ghi quá một lần trong file. Kết quả: Cho trong file văn bản XEPMA.OUT, gồm một số nguyên K duy nhất thể hiện số quân mã nhiều nhất có thể đặt trên bàn cờ sao cho không có quân mã nào ăn nhau. Ví dụ: XEPMA.INP XEPMA.OUT 3 2 1 1 3 3 5 Lưu ý: • Thí sinh không được sử dụng readln trong chương trình. • Thí sinh vi phạm một trong các quy định nêu trên sẽ bị 0 điểm bài thi. (Giám thị không được giải thích gì thêm) HẾT trang 3/3