KỲ THI OLYMPIC TRUYỀN THỐNG 30/4
LẦN THỨ XIII TẠI THÀNH PHỐ HUẾ

ĐỀ THI MÔN TIN HỌC
Thời gian làm bài 180’
Khối 10

Tổng quan đề thi :

Tên bài
DÃY CON
ĐƯỜNG ĐI NGẮN NHẤT
MUA VÉ

File bài làm
Bl1.pas
Bl2.pas
Bl3.pas

Dữ liệu vào
SEQ.INP
PATH.INP
TICK.INP

Dữ liệu ra
SEQ.OUT
PATH.OUT
TICK.OUT

Giới hạn
2 giây
2 giây
2 giây

Chú ý: - Bài thi được làm trên ngôn ngữ Borland Pascal.
- Đề thi gồm có 3 trang.

BÀI 1: DÃY CON
Ta gọi một dãy chia hết hoàn toàn là dãy a1, a2, …, aN với aj chia hết cho ai với iVí dụ: 3, 7, 11, 3 là một dãy con của dãy 6, 3, 11, 5, 7, 4, 3, 11, 5, 3 nhưng 3, 3, 7 không phải là một dãy con của dãy 6, 3, 11, 5, 7, 4, 3, 11, 5, 3 và 3, 15, 60, 720 là một dãy chia hết.
Yêu cầu: Cho một dãy các số nguyên, tìm dãy con chia hết hoàn toàn có độ dài lớn nhất trong dãy đã cho.
Dữ liệu vào: Cho trong file SEQ.INP có cấu trúc:
Dòng đầu chứa N là độ dài của dãy.
Dòng thứ hai chứa N số nguyên ai, mỗi số cách nhau một dấu cách.
Dữ liệu ra: Kết quả ghi vào file SEQ.OUT:
Chứa độ dài lớn nhất của dãy con chia hết hoàn toàn tìm được.
Giới hạn: N <= 10000.
-50000<=ai<=50000.
Ví dụ:

SEQ.INP
SEQ.OUT

9
2 3 7 8 14 39 145 76 320
3




BÀI 2 : ĐƯỜNG ĐI NGẮN NHẤT
Cho lưới ô vuông gồm m dòng, n cột chứa các giá trị 0 hoặc 1. Từ một ô có giá trị 0 được phép đi sang một ô có giá trị 0 và có chung cạnh với ô đó. Không được đi vào bất kì ô nào có giá trị 1. Độ dài đường đi được xác định bởi số các ô vuông thuộc đường đi đó. Đường đi ngắn nhất là đường đi có độ dài nhỏ nhất.
Yêu cầu:
Một người xuất phát từ một ô có giá trị 0 bất kỳ trong lưới. Hãy tìm đường đi ngắn nhất để người đó đi được ra ngoài, tức là đi đến một ô có giá trị 0 nằm ở biên của lưới (ô có ít nhất một cạnh nằm ở đường biên của lưới).
Dữ liệu vào: cho trong file PATH.INP có cấu trúc :
Dòng đầu chứa 2 số nguyên m, n lần lượt là số dòng, số cột của lưới.
Dòng thứ hai chứa 2 số u, v lần lượt là chỉ số dòng, chỉ số cột của ô xuất phát.
m dòng tiếp theo mỗi dòng ghi n số 0 hay 1 lần lượt là giá trị các ô của lưới.
Dữ liệu ra: Kết quả ghi ra file PATH.OUT gồm một dòng ghi độ dài đường đi ngắn nhất. Trường hợp không có đường đi ra ngoài thì ghi số -1.
Giới hạn:
0 < m,n ≤ 250.
1 ≤ u ≤ m; 1 ≤ v ≤ n.
Ví dụ:
PATH.INP
PATH.OUT

7 7
4 4
1111111
1100100
1110001
1000101
1011101
1001001
1101011
6




BÀI 3: MUA VÉ
Có N người xếp hàng mua vé, đánh số 1 đến N theo thứ tự đứng trong hàng. Thời gian phục vụ bán vé cho người thứ i là ti. Mỗi người cần mua một vé nhưng được quyền mua tối đa 2 vé, vì thế một số người có thể nhờ người đứng ngay trước mình mua hộ vé. Người thứ i nhận mua vé cho người thứ i+1 thì thời gian mua vé cho 2 người là ri.
Yêu cầu: Tính thời gian nhỏ nhất để bán vé xong cho N người.
Dữ liệu vào: Đọc từ file TICK.INP
Dòng thứ nhất ghi số N.
Dòng thứ hai ghi N số nguyên dương t1, t2, …, tN
Dòng thứ ba ghi N – 1 số r1, r2, …, rN-1
Dữ liệu ra: Kết quả ghi ra file TICK.OUT
Dòng thứ nhất ghi tổng thời gian phục vụ bán vé
Các dòng tiếp theo ghi chỉ số của các khách hàng cần rời khỏi hàng, mỗi dòng 10 số, ngược lại nếu không có ai rời khỏi hàng ghi số 0.
Giới hạn:
1 < N ≤ 2000.
Ví dụ:
TICK.INP
TICK.OUT

5
2 5 7 8 4
3 9 10 10
17
2 4


---------------------Hết-------------------