Đề thi chọn học sinh giỏi lớp 12 THPT môn Tin học

Trang 1 SỞ GD&ĐT VĨNH PHÚC ——————— ĐỀ CHÍNH THỨC KỲ THI CHỌN HSG LỚP 12 THPT NĂM HỌC 2011 - 2012 ĐỀ THI MÔN: TIN HỌC Dành cho học sinh trường THPT Chuyên Vĩnh Phúc Thời gian làm bài: 180 phút, không kể thời gian giao đề ——————————— Lưu ý: Đề thi có 02 trang Tổng quan: TT Tên bài File chương trình File dữ liệu File kết quả Thời gian Bài 1 Bài 2 Bài 3 Thí sinh có thể thay * bằng PAS hoặc CPP tùy theo ngôn ngữ lập trình. Bài 1. Mua bi Bờm đi mua bi ở siêu thị. Siêu thị có loại bi với màu khác nhau, loại màu siêu thị có hộp, mỗi hộp chứa bi. Giá của mỗi hộp là như nhau và Bờm đủ tiền mua hộp. Cậu muốn mua được nhiều bi nhất có thể. Hãy xác định số bi nhiều nhất Bờm có thể mua được. Dữ liệu (colball.inp):  Dòng : hai số nguyên ( )  Dòng : dòng ghi hai số nguyên ( ) Kết quả (colball.out):  Dòng : số nguyên kết quả. Ví dụ Input Output Giải thích 7 3 5 10 2 5 3 6 62 Bờm mua 5 hộp bi màu 1, 2 hộp bi màu 3. Bài 2. Truyền tin Bờm đi làm thêm ngày Chủ nhật trong một xưởng máy nọ. Xưởng máy có dạng một trục thẳng dài coi như một trục tọa độ. Hiện có công nhân đang làm việc, công nhân thứ làm việc trên một băng chuyền liên tục di chuyển từ vị trí tọa độ đến vị trí tọa độ , rồi lại quay về , … Bờm phải thông báo một tin tức cho cả công nhân. Vì xưởng máy rất ồn nên Bờm chỉ có thể đọc thông báo trực tiếp cho từng người theo nghĩa với mỗi công nhân , Bờm cần một thời điểm ở cùng tọa độ với công nhân đó. Vì thế Bờm có thể di chuyển tới một vị trí nào đó rồi chờ băng chuyền của các công nhân chạy ngang qua. Bờm muốn tối thiểu hóa quãng đường di chuyển. Trang 2 Biết vị trí xuất phát của Bờm, hãy xác định độ dài quãng đường ngắn nhất Bờm cần di chuyển để thông tin cho toàn bộ công nhân. Dữ liệu (w2comm.inp):  Dòng : hai số nguyên ( )  Dòng : dòng ghi hai số nguyên ( ) Kết quả (w2comm.out):  Dòng : số nguyên kết quả. Ví dụ: Input Output Giải thích 3 3 0 7 14 2 4 6 1 Bờm cần di chuyển đến vị trí 4 để thông tin cho công nhân 3. Bài 3. Sửa đường Hệ thống giao thông của thành phố gồm nút đánh số với đường nối trực tiếp giữa các nút. Hệ thống này đảm bảo tính liên thông giữa các nút. Thành phố giao cho Sở giao thông công chính lập dự án cải tạo hai tuyến đường, mỗi tuyến là một dãy các nút sao cho hai nút liên tiếp có đường đường nối trực tiếp. Hai tuyến đường được cải tạo phải không có giao cắt, nghĩa là không có nút giao thông chung. Kinh phí cấp cho dự án sẽ bằng tích độ dài hai tuyến (độ dài mỗi tuyến bằng số đường nối trực tiếp trên tuyến đó). Cho thông tin về hệ thống giao thông, hãy xác định kinh phí được cấp lớn nhất có thể. Dữ liệu (p2path.inp):  Dòng : số nguyên ( )  Dòng : mỗi dòng hai số nguyên ( ) chỉ một đường nối trực tiếp hai nút giao thông . Kết quả (p2path.out):  Dòng : số nguyên kết quả. Ví dụ Input Output Giải thích 6 1 2 2 3 2 4 5 4 6 4 4 Hai tuyến đường được chọn là (1,2, 3) và (5, 4, 6) --------Hết-------- Giám thị coi thi không giải thích gì thêm Họ tên thí sinh………………………………………………………….SBD……………