Đề thi học sinh giỏi lớp 12 THPT cấp Thành phố năm 2006 - 2007 môn Tin học - Sở Giáo dục và Đào tạo TP Hồ Chí Minh

Mời các bạn tham khảo Đề thi học sinh giỏi lớp 12 THPT cấp Thành phố năm 2006 - 2007 môn Tin học của Sở Giáo dục và Đào tạo TP Hồ Chí Minh sau đây để biết được cấu trúc đề thi cũng như những dạng bài chính được đưa ra trong đề thi. Từ đó, giúp các bạn có kế hoạch học tập và ôn thi hiệu quả.

Nội dung trích xuất từ tài liệu:
Đề thi học sinh giỏi lớp 12 THPT cấp Thành phố năm 2006 - 2007 môn Tin học - Sở Giáo dục và Đào tạo TP Hồ Chí MinhSỞ 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 ĐỀ CHÍNH THỨC Khóa ngày: 07/12/2006 (gồm có 3 trang) 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.OUTBài 2 Biểu diễn BIEUDIEN.PAS BIEUDIEN.INP BIEUDIEN.OUTBài 3 Sắp xếp mã XEPMA.PAS XEPMA.INP XEPMA.OUTBà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 đốinhỏ 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.OUT6 4 6 0510-5-624 trang 1/3Bà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 (2 a)(3b) saocho 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êndươ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+1của file BIEUDIEN.INP.Ví dụ: BIEUDIEN.INP BIEUDIEN.OUT4 11 27 116 331 trang 2/3Bà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