đề tỉnh quảng nam 2014 -2015

SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI HỌC SINH GIỎI LỚP 9 CẤP TỈNH
QUẢNG NAM Năm học 2014 - 2015
Môn thi : TIN HỌC
Thời gian : 150 phút (không kể thời gian giao đề)
Ngày thi : 10/4/2015

Tổng quan về đề thi
Bài Bài làm Dữ liệu vào Dữ liệu ra
Bài 1: Chọn chuyến xe buýt BL1.PAS BUS.INP BUS.OUT
Bài 2: Trò chơi truyền hình BL2.PAS GAMESHOW.INP GAMESHOW. OUT
Bài 1: Hai hình chữ nhật BL3.PAS HCN.INP HCN. OUT

Bài 1: (7 điểm). Chọn chuyến xe buýt.
Có một trạm xe buýt ở vùng quê nọ rất uy tín với khách nhờ việc lập lịch khoa học và phục vụ tốt. Chuyến xe buýt khởi hành đầu tiên đi về các tuyến vào buổi sáng, thời gian To và cách một khoảng thời gian D lại có chuyến xe kế tiếp khởi hành để chở khách. Mỗi ngày doanh nghiệp xe buýt này có Ci chuyến, chuyến thứ I khởi hành vào lúc To + (i-1)xD, chuyến 1 khởi hành lúc To.
Có N hành khách thường xuyên đi xe buýt tại bến, hành khách thứ j đến bến ở thời điểm sj và muốn người quản lý trạm xe buýt cho biết rõ chuyến đi để chủ động công việc.
Yêu cầu: Cho To, D và thời điểm các hành khách đến bến, hãy giúp nhà quản lý trạm xe xác định số thứ tự chuyến xe buýt để khách hàng đi.
Dữ liệu vào: File văn bản BUS.INP
+ Dòng thứ nhất chứa ba số nguyên N, D, To (2≤N≤100;1≤N≤100; 0≤N≤100).
+ Dòng thứ hai chứa N số nguyên S1, S2,…,SN (0≤Sj≤103).
Dữ liệu ra: Ghi ra file văn bản BUS.OUT
Gồm một dòng chứa N số nguyên dương, mỗi số nguyên dương là số thứ tự chuyến xe buýt mà hành khách đi.
Ví dụ:
BUS.INP BUS.OUT
3 5 8
0 15 23 1 3 4

Bài 2 (7 điểm). Trò chơi truyền hình.
Một trò chơi dành cho nhiều đội chơi được Ban tổ chức quy định như sau: bắt đầu cuộc chơi, Ban tổ chức cho chạy N số trên màn hình từ trái sang phải và yêu cầu đội chơi nào trả lời nhanh nhất số cách chia dãy số trên thành nhiều dãy con nhất sao cho các dãy con có tổng bằng nhau.
Ví dụ: Trên màn hình chạy dòng 19 số: 1 0 2 0 0 3 1 1 1 0 2 1 0 0 2 1 2 0 1. Kết quả trả lời đúng là: tổng các số mỗi dãy con là 3, số dãy con nhiều nhất là 6, bao gồm các dãy con là: 1 0 2, 0 0 3, 1 1 1, 0 2 1, 0 0 2 1, 2 0 1
+Dữ liệu vào: File văn bản GAMESHOW.INP
- Dòng 1 chứa số nguyên dương N.
- Dòng 2 chứa N số chạy trên màn hình, các số cách nhau bởi dấu cách.
+ Dữ liệu ra: Ghi ra file văn bản GAMESHOW.OUT
- Dòng 1 là tổng các số của một dãy con.
- Dòng 2 là số K (số dãy con nhiều nhất chia được).
- Dòng 3 là các vị trí cuối cùng của từng dãy con, các số vị trí này cách nhau bởi dấu cách.
Ví dụ:
GAMESHOW.INP GAMESHOW.OUT
19
1 0 2 0 0 3 1 1 1 0 2 1 0 0 2 1 2 0 1 3
6
3 6 9 12 16 19
Bài 3 67 điểm). Hai hình chữ nhật.
Cho một bảng các ô vuông đơn vị có kích thước nxm (n, m ≤ 100; n số hàng, m số cột của bảng). Trên mỗi ô vuông đơn vị chứa các số nguyên dương.
Yêu cầu: Hãy tìm ở bảng trên hai hình chữ nhật (có thể giao nhau nhưng không trùng khít lên nhau) có kích thước pxq (p<n; q<m; p là số hàng, q là số cột của hai hình chữ nhật con) sao cho tổng của tất cả các số trên hai hình chữ nhật là lớn nhất.
Dữ liệu vào: File tên HCN.OUT
- Dòng 1 ghi bốn số n, m, p, q được ghi cách nhau bởi dấu cách.
- n dòng tiếp theo, mỗi dòng ghi m số nguyên dương và cách nhau bởi dấu cách.
Dữ liệu ra: File HCN.OUT, chứa 1 dòng ghi một số nguyên duy nhất S là diện tích lớn nhất cần tìm.
HCN.INP HCN.OUT
4 7 3 3
1 2 3 1 1 3 4
5 3 1 4 0 1 2
4 6 3 4 7 1 1
9 3 8 10 0 1 0 84
Ví dụ:
1 2 3 1 1 3 4
5 3 1 4 0 1 2
4 6 3 4 7 1 1
9 3 8 10 0 1 0