Đề thi chọn học sinh giỏi quốc gia Lớp 12 THPT năm 2006 môn Tin học (Bảng A - Đề 1) (Có đáp án)

BỘ GIÁO DỤC VÀ ĐÀO TẠO 	 KÌ THI CHỌN HỌC SINH GIỎI QUỐC GIA
	 LỚP 12 THPT NĂM 2006
§Ò Thi ChÝnh thøc
Môn: TIN HỌC - Bảng A
Thời gian: 180 phút (Không kể thời gian giao đề)
Ngày thi thứ nhất: 23/02/2006
(Đề thi gồm 2 trang)
TỔNG QUAN BÀI THI 
Tên bài
Tên chương trình
File dữ liệu vào
File kết quả
BÀI 1
Dãy con dài nhất
MAXSEQ.PAS
MAXSEQ.INP
MAXSEQ.OUT
BÀI 2
Đường đi trên lưới
NETPATH.PAS
NETPATH.INP
NETPATH.OUT
Hãy lập trình giải các bài toán sau:
Bài 1. Dãy con dài nhất
Cho dãy số nguyên
a1, a2, ..., an.
Dãy số
ai, ai+1, ..., aj
với 1£ i £ j £ n được gọi là dãy con của dãy số đã cho và khi đó, j-i+1 được gọi là độ dài, còn được gọi là trọng lượng của dãy con này. 
Yêu cầu: Cho số nguyên p, trong số các dãy con của dãy số đã cho có trọng lượng không nhỏ hơn p hãy tìm dãy con có độ dài lớn nhất.
Dữ liệu: Vào từ file văn bản MAXSEQ.INP:
Dòng đầu tiên ghi hai số nguyên n và p cách nhau bởi dấu cách;
Dòng thứ i trong số n dòng tiếp theo chứa số nguyên ai là số hạng thứ i của dãy số đã cho, i = 1, 2, ..., n.
Kết quả: Ghi ra file văn bản MAXSEQ.OUT số nguyên k là độ dài của dãy con tìm được (qui ước: nếu không có dãy con nào thoả mãn điều kiện đặt ra thì k = -1) .
Ví dụ:
MAXSEQ.INP
MAXSEQ.OUT
MAXSEQ.INP
MAXSEQ.OUT
5 6 
-2 
3 
2 
-2
3
4
4 9 
2 
3 
2 
-2
-1
Hạn chế: Trong tất cả các test: 1 £ n £ 20000; | ai | £ 20000; | p | £ 109. Có 50% số lượng test với n £ 1000.
Bài 2. Đường đi trên lưới
Cho một lưới ô vuông gồm m dòng và n cột. Các dòng được đánh số từ 1 đến m từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái qua phải. Ô nằm ở vị trí dòng i và cột j của lưới được gọi là ô (i,j) và khi đó, i được gọi là toạ độ dòng còn j được gọi là toạ độ cột của ô này. Trên ô (i,j) của lưới ghi số nguyên dương aij, i = 1, 2, ..., m; j = 1, 2, ..., n. Trên lưới đã cho, từ ô (i,j) ta có thể di chuyển đến ô (p,q) nếu các điều kiện sau đây được thoả mãn:
j < n; i £ p; j £ q và i + j < p + q; 
aij và apq có ước số chung lớn hơn 1.
Ta gọi một cách di chuyển từ mép trái sang mép phải của lưới là cách di chuyển bắt đầu từ một ô có toạ độ cột bằng 1 qua các ô của lưới tuân theo qui tắc di chuyển đã nêu và kết thúc ở một ô có toạ độ cột bằng n.
Yêu cầu: Tính số cách di chuyển từ mép trái sang mép phải của lưới.
Dữ liệu: Vào từ file văn bản NETPATH.INP:
Dòng đầu tiên ghi 2 số nguyên dương m, n.
Dòng thứ i trong số m dòng tiếp theo ghi n số nguyên dương ai1, ai2, ..., ain là các số trên dòng thứ i của lưới, i = 1, 2, ..., m.
 Hai số liên tiếp trên cùng một dòng được ghi cách bởi ít nhất một dấu cách.
Kết quả: Ghi ra file văn bản NETPATH.OUT số nguyên k là số lượng cách di chuyển tìm được, biết rằng dữ liệu đảm bảo k < 109.
Ví dụ:
NETPATH.INP
NETPATH.OUT
NETPATH.INP
NETPATH.OUT
2 2
2 4
6 8
4
2 2
2 5
6 7
0
Hạn chế: Trong tất cả các test: 1 < m, n £ 100; aij £ 30000, i=1,2,...,m; j=1,2,...,n. Có 50% số lượng test với m, n £ 50.
-------------- HẾT ------------------
Thí sinh không được sử dụng tài liệu.
Giám thị không giải thích gì thêm.