Đề thi HSG cấp tỉnh môn Tin 9 năm 2018 Sở GD&ĐT Bình Định

Tổng quan đề thi:                             (Đề thi có hai trang)

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ụ :

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).