ĐỀ VÀ ĐÁP ÁN _ HSG ĐBSCL _XVI - 2009¬_Long An_ Tin

SỞ GIÁO DỤC VÀ ĐÀO TẠO LONG AN
TRƯỜNG THPT LÊ QUÍ ĐÔN
Năm học 2008-2009
MÔN TIN HỌC

Đề thi đề nghị

DÃY CON TĂNG NGUYÊN TỐ

Cho 1 dãy N số nguyên dương. Dãy con tăng nguyên tố M phần tử là 1 dãy số có dạng
Ai1 Ai2 Ai3 … Aim
Và thỏa điều kiện
1 <= i1 < i2 < i3 < … < im <= n
Ai1 <= Ai2 <= Ai3 <= … <= Aim
Ai là số nguyên tố (số nguyên tố là số chỉ có đúng 2 ước số là 1 và chính nó)

Hãy tìm độ dài của dãy con tăng nguyên tố dài nhất

Dữ liệu nhập: vào từ file DAYCON.INP với định dạng như sau:
_ Dòng đầu tiên là số N <= 1000 (tức là số phần tử của dãy số ban đầu)
_ Các dòng tiếp theo chứa N số nguyên là giá trị các phần tử của dãy số (0<=A[i]<=100000)

Dữ liệu xuất: xuất ra file DAYCON.OUT
_ Số đầu tiên là số M tức phần tử của dãy con tăng nguyên tố dài nhất
_M dòng sau ghi ra giá trị các phần tử của dãy con tăng dài nhất
DAYCON.inp
DAYCON.out

13
3 13 6 8 7
12 9 5
11 6 3 13
15
4
3 7 4 3


(Giải thích: dãy con tăng nguyên tố dài nhất có 4 phần tử là 3 7 11 13)
ĐƯỜNG ĐI TRÊN MA TRẬN

Cho 1 bảng số kích thước MxN. Bảng số có M dòng đc đánh số từ trên xuống dưới và N cột đánh số từ trái sang phải. Cặp tọa độ (i,j) biểu diễn ô có vị trí dòng i cột j. Mỗi ô (i,j) chứa một số nguyên A[i,j] (|A[i]| <= 30000). Bắt đầu từ 1 ô ở cột đầu tiên, ta di chuyển đến cột kế tiếp cho đến khi đến cột N. Từ ô (i,j) ta có thể di chuyển đến 1 trong 3 ô (i-1,j+1) hoặc (i,j+1) hoặc (+1,j+1). Chú ý là ta chỉ có thể đi đến ô (i,j) nếu 1 <= i,j <= N. Trọng số của đường đi là tổng các số trên đường đi đó. Hãy tìm đường đi có trọng số lớn nhất bắt đầu từ một ô bất kì ở cột 1 đến một ô bất kì ở cột N.

Dữ liệu nhập: vào file BANG.inp
_ Dòng đầu chứa 2 số M,N (1<= M,N <=100)
_M dòng sau mỗi dòng chứa N số nguyên trong khoảng [-30000..30000] là giá trị của các ô

Dữ liệu xuất: ra file BANG.out
_ 1 số duy nhất là trọng số lớn nhất tìm được.

BANG.inp
BANG.out

4 5
3 2 6 5 9
7 10 6 4 3
11 7 8 2 5
9 8 4 3 1
42


Giải thích:

3
2
6
5
9

7
10
6
4
3

11
7
8
2
5

9
8
4
3
1


TEST BÀI ĐƯỜNG ĐI TRÊN MA TRẬN

TEST 1:
10
6 8 4 4 9 5 6 3 7 0
4 3 8 9 7 6 7 7 2 9
5 7 5 4 7 3 0 0 0 2
3 1 2 6 5 7 4 5 4 6
3 7 0 8 0 6 8 7 7 4
4 7 8 2 8 6 7 8 8 4
6 8 4 8 6 3 8 1 5 4
8 9 6 8 2 1 2 1 7 4
0 7 7 6 3 6 5 5 6 4
9 1 6 7 7 9 3 4 4 1

( 45

TEST 2:
10 10
9 0 0 3 8 8 7 9 3 3
4 6 4 7 0 1 7 3 7 7
2 9 1 6 5 0 3 6 6 2
0 0 2 1 2 1 1 6 0 8
6 6 2 7 1 6 2 0 0 4
5 3 2 6 8 2 2 3 2 0
9 3 0 2 5 6 0 8 3 1
1 3 2 5 0 1 1 1 5 5
0 3 0 3 4 8 4 4 4 5
0 9 9 8 4 0 2 3 9 8

( 72

TEST 3:
50 10
5 8 0 3 2 2 8 4 2 3
7 7 0 1 0 6 6 1 7 4
0 0 3 4 4 6 5 0 4 4
3 7 7 2