Đề thi HSGQG Môn Tin học ngày thứ nhất 2011
Bài 1(Tóm tắt):
Cho bảng N*N (n<=1000, 1<=a[i,j]<=1000),hãy tìm 1 bảng con k*k (n/3<=k<=n) sao tổng giá trị các số trong bảng lớn nhất.
Bài 2(Tóm tắt):
Cho n điểm trên Oxy, (n<=10^5), |x[i],y[i]|<=200,mỗi điểm cho 1 màu.Hãy đếm số HCN có cạnh song song vối trục tọa độ và 4 đỉnh của HCN 4 màu khác nhau.
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 sắp 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 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.
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 giố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 <= 10^5, h <= 10^6.
* 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 sắp 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 10^9.
Ví dụ:
TREELINE.INP
2 2011
11 1
TREELINE.OUT
2
5
Ràng buộc: 50% số tests ứng với 50% số điểm của bài có 2 <= n <= 15
