Đề và đán án đề thi HSG môn Tin học tỉnh Ninh Bình năm 2007-2008(vòng 1)

Sở giáo dục và đào tạo Đề thi chọn học sinh giỏi lớp 12 THPT
Tỉnh ninh bình năm học 2007 - 2008
Môn: Tin học (Vòng 1)
Thời gian làm bài: 180 phút (không kể thời gian giao đề)

Đề thi gồm 03 bài trong tổng số 03 trang


Tên bài
Tên file chương trình
File dữ liệu vào
File kết quả

Bài 1
Dịch cúm gia cầm
H5N1.PAS
H5N1.INP
H5N1.OUT

Bài 2
Đóng cửa sổ
WINDOWS.PAS
WINDOWS.INP
WINDOWS.OUT

Bài 3
Lịch trình xe buýt
ITINE.PAS
ITINE.INP
ITINE.OUT


Bài 1 - H5N1 (8 điểm):
H5N1 là một loại virus cúm phát triển mạnh trong các đàn gia cầm (gà, vịt…) sau đó có thể lây lan sang người. Phương pháp phổ biến hiện nay để ngăn chặn sự lây lan của H5N1 là tiêu huỷ gia cầm ở nơi có ảnh hưởng của dịch và để ngăn chặn nguy cơ tái phát dịch. Một trong những nguyên tắc tiêu huỷ gia cầm là phải tiêu huỷ toàn bộ gia cầm (nếu tồn tại, dù chỉ một con gia cầm trong vùng thì cũng coi như việc tiêu huỷ là vô ích).
Cả nước có N địa phương, các địa phương được đánh số thứ tự lần lượt: 1, 2, 3,…N. Ban chỉ đạo phòng chống dịch Trung ương đã tính toán được chi phí cần thiết cho việc dập dịch tại địa phương thứ i là Ti.
Với một số tiền K được nhà nước cung cấp, hãy chỉ ra một phương án giúp Ban chỉ đạo phòng chống dịch Trung ương phân bổ số tiền này cho các địa phương cần dập dịch theo tính toán trên sao cho số địa phương được nhận tiền đủ để dập dịch là nhiều nhất.
Dữ liệu vào: File văn bản H5N1.INP:
Dòng thứ nhất ghi số nguyên dương N (N ( 30000), và K ( K ( 2*109 ).
Trong N dòng tiếp theo, dòng thứ i ghi một số tự nhiên Ti (Ti ( 50000). Nếu địa phương thứ i không cần dập dịch thì Ti = 0.
Dữ liệu ra: File văn bản H5N1.OUT:
Dòng đầu ghi một số nguyên là số địa phương nhiều nhất có thể nhận được tiền. Nếu không có đáp án ghi một số 0.
Dòng tiếp theo ghi số thứ tự của các địa phương được nhận tiền nếu có đáp án. Hai số cạnh nhau ngăn cách bằng một ký tự cách.
Ví dụ:
H5N1.INP
H5N1.OUT

4 10
8
9
1
2
2
1 3

Bài 2 - Đóng cửa sổ (8 điểm):
Trong giao diện đồ hoạ của một hệ điều hành, màn hình được chia thành một lưới các ô vuông. Trên lưới, một ô vuông được định vị bằng toạ độ (x, y) : cột x, dòng y. Một cửa sổ được định nghĩa là một tập các ô vuông tạo thành một hình chữ nhật. Cửa sổ được xác định khi biết toạ độ (u, v) của ô góc trên bên trái và toạ độ (x, y) của ô góc dưới bên phải.
Có thể mở được nhiều cửa sổ trên màn hình, khi đó cửa sổ mở sau có thể sẽ che khuất một phần của các cửa sổ mở trước. Người sử dụng hệ điều hành đóng một cửa sổ bằng cách nháy chuột lên ô vuông góc trên bên phải của cửa sổ, như vậy một cửa sổ chỉ có thể đóng lại được khi ô vuông ở góc trên bên phải của