Sau đây là "Đề thi chọn đội tuyển học sinh giỏi lớp 12 môn: Tin học" năm học 2014-2015. Mời các bậc phụ huynh, thí sinh và thầy cô giáo cùng tham khảo để để có thêm tài liệu phục vụ nhu cầu học tập và ôn thi. Chúc các bạn đạt kết quả cao trong kỳ thi sắp tới. | SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HOÁ ĐỀ THI CHỌN ĐỘI TUYỂN HSG LỚP 12 THPT NĂM HỌC 2014 – 2015 MÔN THI: TIN HỌC Ngày thi: 07 – 03 – 2015 Thời gian 150 phút, không kể thời gian giao đề (Đề gồm 3 câu, 2 trang) Tổng quan bài thi: Câu Tên bài Tên file nguồn Tên file input Tên file output số test 1 Hiệu số Bai1. PAS 18 2 Ước chung lớn nhất Bai2. inp Bai2. out 14 3 Hàn sắt Bai3. inp Bai3. out 16 Hãy lập trình giải các bài toán sau: Câu 1. Hiệu số Cho một dãy gồm n số nguyên a1, a2, ., an. Hãy tìm hai chỉ số i, j sao cho i < j và hiệu aj - ai là lớn nhất. Dữ liệu vào: Từ file ồm 2 dòng: - Dòng 1: Là số nguyên n (2 ≤ n ≤ 106) - Dòng 2: Gồm n số nguyên a1, a2, ., an (0 ≤ ai ≤ 109) Kết quả ra: Ghi vào tệp giá trị lớn nhất của hiệu aj - ai. Ví dụ: 4 2 5 1 3 3 Câu 2: Ước chung lớn nhất An mới bắt đầu học toán và cậu ta vẫn chưa biết gì về ước số chung lớn nhất. Cho nên cậu ta cần sự giúp đỡ của bạn để làm một vài phép toán. An có một dãy A gồm N số nguyên, được đánh số từ 1 đến N và An muốn tạo một mảng B gồm N+1 phần tử được đánh số từ 1 đến N+1 và các phần tử của mảng B có tính chất sau: UCLN(B[i], B[i + 1]) = A[i], ∀ 1 ≤ i ≤ N. Nếu như có nhiều kết quả thì bạn chỉ cần cho An biết mảng B có tổng các phần tử là nhỏ nhất (vì cậu ta chỉ mới bắt đầu học toán nên rất ngại các con số lớn). Dữ liệu vào: Từ file Bai2. inp dòng đầu tiên chứa một số nguyên T là số lượng test (1 ≤ T ≤ 10). Tiếp theo là các test case: Dòng đầu tiên của mỗi test case chứa một số nguyên dương N - số lượng phần tử của mảng A (2 ≤ N ≤ 105). Dòng thứ hai chứa N số nguyên A1 A2 . AN (1 ≤ Ai ≤ 109) Kết quả ra: Ghi vào tệp Bai2. out mảng B ứng với mỗi test. Ví dụ Bai2. inp Bai2. out 2 3 1 2 3 3 5 10 5 1 2 6 3 5 10 10 5 Câu 3. Hàn sắt Anh Bo có n cây sắt lần lượt có chiều dài là a1, a2,., an. Anh muốn hàn n cây sắt trên thành một cây duy nhất có chiều dài a1+ a2+ . + an. Cách thực hiện là chọn 2 cây sắt bất kỳ hàn lại thành một cây và cứ tiếp tục như vậy cho đến khi chỉ còn lại một cây duy nhất. Để hàn 2 cây sắt có chiều dài x và y thì cần tốn chi phí là x+y. Bạn hãy giúp anh Bo tìm thứ tự hàn sao cho chi phí hàn là nhỏ nhất nhé. Dữ liệu vào: từ file gồm 2 dòng - Dòng thứ nhất là số nguyên n (1 ≤ n ≤ 106) là số lượng cây sắt. - Dòng thứ hai gồm n số nguyên a1, a2,., an (1 ≤ ai ≤ 109) là chiều dài của các cây sắt. Kết quả: Ghi vào tệp một số nguyên là chi phí tối thiểu để hàn các thanh sắt. Ví dụ Bai3. inp Bai3. out 7 8 4 2 2 3 1 1 53 Giải thích: Thứ tự hàn sắt như sau: Tổng chi phí hàn: 2 + 4 + 5 + 8 + 13 + 21 = 53. ------Hết-----
