Đề thi môn tin học thời gian làm bài 180 phút khối 10

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 i<j. Một dãy con của một dãy là một dãy được thiết lập bằng cách xoá một số phần tử nào đó trong dãy. Ví 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-------------------