tailieunhanh - Đề thi HSG quốc gia môn Tin lớp 12 năm 2011

Mời các bạn học sinh tham khảo đề thi học sinh giỏi quốc gia môn Tin học lớp 12 năm 2011 ngày thứ 1 nhằm giúp cho bạn luyện tập và củng cố kiến thức Tin học về: Ngôn ngữ lập trình Pascal, ngôn ngữ lập trình C++. . | BỘ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI QUỐC GIA ĐỀ THI CHÍNH THỨC 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. Bài 2 Hình chữ nhật bốn màu COLOREC. Bài 3 Hàng cây TREELINE. 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 X 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ố từ 1 đến n từ trái qua phải. Ô nằm trên giao của dòng i và cột j được gọi là ô i j và trên ô đó chứa một món quà có giá trị là ay 1 i j n . Để nhận phần thưởng Tuấn được phép chọn một hình vuông kích thước k X k chiếm trọn một số ô của bảng và nhận tất cả các phần quà trong các ô nằm trong hình vuông đó. Yêu cầu Hãy xác định tổng giá trị lớn nhất của các món quà mà Tuấn có thể nhận được. Dữ liệu Vào từ file văn bản Dòng thứ nhất chứa hai số nguyên dương n k n 1000 3 k n . Dòng thứ i trong số n dòng tiếp theo chứa n số nguyên dương số thứ j là aịj aj 1000 . 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 một số nguyên duy nhất là tổng giá trị lớn nhất của các món quà mà Tuấn có thể nhận được. Ví dụ Ràng buộc 50 số tests ứng với 50 số điểm của bài có n 100. Trang 1 3 Bài 2. 7 điểm Hình chữ nhật bốn màu Trên mặt phẳng toạ độ Đề các vuông góc Oxy cho n điểm phân biệt Ai xi yi i 1 2 . n. Mỗi điểm Ai được tô bởi màu ci e 1 2 3 4 . Ta gọi hình chữ nhật bốn màu là hình chữ nhật thoả