Đề thi chọn học sinh giỏi Quốc gia Lớp 12 THPT năm 2011 môn Tin học - Ngày 1 (Có đáp án)

BỘ GIÁO DỤC VÀ ĐÀO TẠO 
ĐỀ THI CHÍNH THỨC 
KỲ THI CHỌN HỌC SINH GIỎI QUỐC GIA 
LỚP 12 THPT NĂM 2011 
Môn: TIN HỌC 
Thời gian: 180 phút (không kể thời gian giao đề) 
Ngày thi thứ nhất: 11/01/2011 
(Đề thi có 03 trang, gồm 03 bài) 
TỔNG QUAN NGÀY THI THỨ NHẤT 
 Tên bài File chương trình File dữ liệu vào File kết quả 
Bài 1 Phần thưởng BONUS.* BONUS.INP BONUS.OUT 
Bài 2 Hình chữ nhật bốn màu COLOREC.* COLOREC.INP COLOREC.OUT 
Bài 3 Hàng cây TREELINE.* TREELINE.INP TREELINE.OUT 
Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình được sử dụng tương ứng là Pascal hoặc C++. 
Hãy lập trình giải các bài toán sau: 
Bài 1. (6 điểm) Phần thưởng 
Tuấn là người thắng cuộc trong một cuộc thi “Tìm hiểu kiến thức vũ trụ” và được nhận các phần 
thưởng do công ty XYZ tài trợ. Các phần thưởng được bố trí trên một bảng vuông kích thước n × n 
có dạng một lưới ô vuông kích thước đơn vị. Các dòng của bảng được đánh số từ 1 đến n, từ trên 
xuống dưới và các cột của bảng được đánh s...1 
0 1 4 
2 1 2 
2 -1 3 
0 -1 1 
-1 -1 4 
-1 1 1 
2 
Ràng buộc: 50% số tests ứng với 50% số điểm của bài có 4 ≤ n ≤ 100. 
Bài 3. (7 điểm) Hàng cây 
Một trang trại lớn có n cây cảnh với độ cao khác nhau từng đôi. Các cây này được xếp theo một 
hàng dọc. Ông chủ trang trại là người có đầu óc thẩm mỹ nên hàng cây được bố trí có tính chất 
không đơn điệu sau đây: “Đi từ đầu hàng đến cuối hàng không có 3 cây (không nhất thiết phải liên 
tiếp) có chiều cao giảm dần”. 
Một hôm ông chủ mua thêm một cây cảnh mới có chiều cao lớn hơn chiều cao của tất cả các cây 
đã có. Ông ta muốn xếp cây cảnh mới vào một trong n +1 vị trí có thể của hàng cây đang có (vào 
vị trí đầu hàng, vị trí sau cây thứ nhất của hàng, vị trí sau cây thứ hai của hàng, ..., vị trí sau cây 
thứ n của hàng) sao cho hàng cây thu được vẫn thỏa mãn yêu cầu về tính không đơn điệu nêu trên. 
Trang 2/3 
Yêu cầu: 
• Hãy cho biết có bao nhiêu cách xếp cây cảnh cao nhất mới mua vào hàng cây sao cho vẫn 
đảm bảo điều kiện về tính không đơn điệu. 
• Giả sử mỗi ngày ông chủ muốn xếp n+1 cây đã có thành hàng cây đảm bảo yêu cầu về tính 
không đơn điệu và hai hàng cây của hai ngày khác nhau là không trùng nhau, hãy giúp ông 
chủ tính xem việc đó có thể diễn ra nhiều nhất là bao nhiêu ngày. 
Dữ liệu: Vào từ file văn bản TREELINE.INP 
• Dòng thứ nhất chứa hai số nguyên dương n và h tương ứng là số lượng cây và chiều cao 
của cây cao nhất. Biết rằng n ≤ 105, h ≤ 106. 
• Dòng thứ hai chứa n số nguyên dương (mỗi số đều nhỏ hơn h) tương ứng là dãy chiều cao 
của n cây được xếp ban đầu. 
Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách. 
Kết quả: Ghi ra file văn bản TREELINE.OUT 
• Dòng thứ nhất ghi một số nguyên là số cách xếp cây cao nhất vào hàng cây. 
• Dòng thứ hai ghi một số nguyên là phần dư trong phép chia số ngày lớn nhất tìm được cho 109. 
Ví dụ: 
TREELINE.INP TREELINE.OUT
2 2011 
11 1 
2 
5 
Ràng buộc: 50% số tests ứng với 50% số điểm của bài có 2 ≤ n ≤ 15. 
-