| SỞ GIÁO DỤC VÀ ĐÀO TẠO | KỲ THI HỌC SINH GIỎI CẤP TỈNH LỚP 9 Môn thi: TIN HỌC Thời gian: 150 phút (không kể thời gian phát đề)
|
Tổng quan đề thi: (Đề thi có hai trang)
| Bài | Tên bài | Tên tệp | Tên tệp | Tên tệp |
| 1 | Đoạn con có tổng lớn nhất (6,0 điểm) | DOANCON.PAS | DOANCON.INP | DOANCON.OUT |
| 2 | Hình vuông lớn nhất (7,0 điểm) | VUONG.PAS | VUONG.INP | VUONG.OUT |
| 3 | Phân rã nguyên tố (7,0 điểm) | PR_NGTO.PAS | Bàn phím | Màn hình |
Bài 1. Đoạn con có tổng lớn nhất (6,0 điểm)
Cho một dãy gồm N số nguyên a1, a2,…, aN (N<250). Một đoạn con của dãy từ phần tử thứ p đến phần tử thứ q gồm liên tiếp các số ap, …, ap (1<=p<=q<=N). Hãy viết chương trình tìm một đoạn con có tổng lớn nhất của dãy N số đã cho.
Dữ liệu vào là file DOANCON.INP có cấu trúc như sau:
- Dòng thứ nhất chứ số nguyên N.
- Dòng tiếp theo chứa N số nguyên a1, a2, …, aN; các số kề nhau cách nhau một khoảng trắng.
Dữ liệu ra là file DOANCON.OUT có cấu trúc như sau :
- Dòng thứ nhất chứa một số là tổng các phần tử của đoạn con tìm được.
- Dòng thứ 2 gồm hai số nguyên dương p, q chỉ vị trí bắt đầu và vị trí kết thúc của đoạn con trong dãy.
Ví dụ :
| DOANCON.INP |
| DOANCON.OUT | Giải thích |
| 10 1 -2 -3 5 7 -1 4 -2 -4 1 |
| 15 4 7 | Đoạn con 5 7 -1 4
|
Bài 2. Hình vuông lớn nhất (7,0 điểm)
Cho một bảng số gồm M dòng, N cột (1<=M, N<=100) mỗi ô được ghi số 1 hoặc số 0. Bài toán đặt ra là tìm một hình vuông có kích thước lớn nhất k trong bảng số nói trên mà trong đó chỉ gồm toàn số 0 hoặc toàn số 1.
Dữ liệu vào là file VUONG.INP có cấu trúc như sau:
- Dòng đầu tiên gồm hai số nguyên M, N. Hai số cách nhau một khoảng trắng.
- M dòng tiếp theo, mỗi dòng gồm N số 0 hoặc 1, các số cách nhau một khoảng trắng để mô tả một dòng của bảng số đã cho.
Dữ liệu ra là file VUONG.OUT có cấu trúc như sau:
- Dòng thứ nhất chứa số nguyên dương k là kích thước của hình vuông lớn nhất tìm được.
- Dòng thứ hai chứa 2 số nguyên dương p, q là tọa độ của góc trên bên trái cảu hình vuông tìm được (dòng p cột q).
