Đề và đáp án Môn Tin 10 Olimpic 30/4 năm 2007

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