Sở Giáo dục và Đào tạo
Vĩnh Phúc
ĐỀ THI CHỌN HỌC SINH GIỎI
MÔN: TIN HỌC 10
NĂM HỌC 2007-2008

 Thời gian làm bài 180 phút không kể thời gian giao đề

Chú ý: Các file chương trình đặt tên lần lượt là: BL1.PAS; BL2.PAS; BL3.PAS
Đề thi có: 03 trang

Bài 1: Dãy con
Cho dãy số nguyên dương {aN} = {a1, a2, …, aN} (N<=1000). Tìm dãy con nhiều phần tử nhất (không nhất thiết liên tiếp và có ít nhất 3 phần tử) của dãy đã cho sao cho bất kì 3 số hạng khác nhau của dãy con: ai, aj, ak đều có ai + aj + ak không lớn hơn tổng các số hạng còn lại của dãy con.
Dữ liệu vào: ‘DAYCON.INP’
Dòng 1: số N là số các phần tử của dãy {aN}
Dòng 2: gồm N số nguyên dương ai , i = 1..N, các ai không lớn hơn 106.
Dữ liệu ra: ‘DAYCON.OUT’
Một số nguyên duy nhất là số lượng phần tử của dãy con tìm được.
Ví dụ:





Bài 2: Địa hình sân bay trực thăng
Địa hình sân bay trực thăng là một khu đất hình chữ nhật có kích thước MxN, được chia thành MxN ô vuông đơn vị, với các đường chia song song với các cạnh của khu đất, các ô vuông được đánh số theo thứ tự từ trên xuống dưới (dòng) và từ trái qua phải (cột). Mỗi ô được đặc trưng bởi một số nguyên không âm tương ứng với độ cao của mặt đất tại ô đó. Mỗi lần máy bay đáp xuống mặt sân tại 4 ô vuông đơn vị tạo thành hình vuông 2x2 và giảm độ cao của mỗi ô trong 4 ô đó đi 1 đơn vị, máy bay sẽ không đáp xuống được nếu trong 4 ô định đáp xuống có ít nhất 1 ô có độ cao là 0.
Yêu cầu:
a, Với địa hình sân bay ban đầu và địa hình sân bay sau một thời gian sử dụng, tính xem đã có bao nhiêu chuyến máy bay đã đáp xuống sân bay?.
b, Với địa hình đã cho ban đầu, chỉ ra vị trí ô trái trên (ô có chỉ số dòng, chỉ số cột nhỏ nhất) trong 4 ô tạo thành hình vuông 2x2 của sân bay mà tại đó máy bay có thể đáp xuống được nhiều nhất.
Chú ý: Nếu có nhiều vị trí mà máy bay cùng đáp xuống được nhiều nhất thì chọn vị trí có chỉ số dòng nhỏ nhất, nếu trên cùng dòng thì chọn vị trí có chỉ số cột nhỏ nhất.
Dữ liệu vào: ’SANBAY.INP’
Dòng 1: M N (M, N nguyên dương và nhỏ hơn hay bằng 100)
M dòng tiếp theo, mỗi dòng N số nguyên không âm (<=1000) cho biết địa hình sân bay ban đầu.
M dòng tiếp theo, mỗi dòng N số nguyên không âm (<=1000) cho biết địa hình sân bay sau một thời gian sử dụng.
Dữ liệu ra: ‘SANBAY.OUT’
Dòng 1: Ghi số k là số chuyến bay đã đáp xuống sân bay.
Dòng 2: Ghi 3 số k, i, j, k - là số chuyến bay có thể đáp xuống nhiều nhất tại vị trí (i,j) - chỉ số dòng và chỉ số cột của ô trái trên (ô có chỉ số dòng, chỉ số cột nhỏ nhất) trong 4 ô tạo thành hình vuông 2x2 của sân bay mà tại đó máy bay có thể đáp xuống được nhiều nhất.
Ví dụ:











Bài 3: Số ô liên tục nhiều nhất trên bàn cờ
Cho một bàn cờ vuông NxN, trên đó cho trước một số quân cờ. Ví dụ hình vẽ sau là một bàn cờ (8x8) như vậy:
 
x
 
x
 
x
 
 

x
 
 
x
x
 
 
x

x
 
x
 
 
 
x
x

 
 
 
x
 
x
 
 

 
 
x
 
 
 
 
 

 
x
 
x
 
 
 
x

x
 
 
x
x
 
 
 

 
x
 
 
 
x
x
 

 
Dữ liệu vào: ‘BANCO.INP’
Dòng 1: số N (<=20) kích thước của bàn cờ
N dòng tiếp theo, mỗi dòng gồn N số 0 hoặc 1, vị trí các quân cờ ứng với số 1, các ô trống ứng với số 0.
Hãy viết chương trình tính