Đề thi HSG QG Tin học

(Đề 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 thỏa 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à tọa độ dòng còn j được gọi là tọa độ 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 thỏa 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ó tọa độ cột bằng 1 qua các ô của lưới theo qui tắc di chuyển đã nêu và kết thúc ở một ô có tọa độ cột bằng n.
Yêu cầu: Tính số cách di chuyển từ mép trái lưới sang mép phải 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.