tailieunhanh - SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH NINH BÌNH ĐỀ THI CHÍNH THỨC ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 12 THPT NĂM HỌC 2010 - 2011 Môn: Tin học - Vòng 2 Thời gian làm bài: 180 phút (không kể thời gian giao đề) (Đề thi gồm 03 bài trong 02 trang) Tổng quan đề thi: Bài 1-

SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH NINH BÌNH ĐỀ THI CHÍNH THỨC ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 12 THPT NĂM HỌC 2010 - 2011 Môn: Tin học - Vòng 2 Thời gian làm bài: 180 phút (không kể thời gian giao đề) (Đề thi gồm 03 bài trong 02 trang) Tổng quan đề thi: Bài 1- Đoạn con 2- Đường đi Chương trình Input Output Thời chạy 1giây/test 1giây/test 1giây/test gian 3- Truyền tin Lưu ý: Thí sinh bắt buộc phải đặt tên file chương trình, file dữ liệu như trên. Bài 1 (7,0 điểm): Đoạn con Cho dãy số nguyên a1, a2,., aN (|ai| (2,1) => (3,1) => (3,2) => (3,3) có tổng: 12 + 4 – 12 + 25 – 4 = 25) (60% số test có N < 13) 25 -12 25 -4 Bài 3 (6,0 điểm): Truyền tin Thời cổ đại, một trong những phương tiện truyền tin hiệu quả sử dụng chim đưa thư. Một vương quốc có N đơn vị hành chính đánh số từ 1 đến N( kinh thành được đánh số là 1). Hệ thống truyền tin được Quốc vương xây dựng như sau: Mỗi đơn vị hành chính có danh sách một số đơn vị khác để khi nhận được một thông tin (từ kinh thành hay từ các đơn vị khác truyền đến) thì sẽ lập tức dùng chim đưa thư truyền tin đến các đơn vị trong .danh sách đó. Khi có một mệnh lệnh cần ban hành nó sẽ được truyền đi từ kinh thành và hệ thống đã xây dựng đảm bảo thông tin đến được với mọi đơn vị hành chính. Sau một thời gian hoạt động, Quốc vương muốn đánh giá hiệu quả của hệ thống truyền tin. Vì thế ngài muốn các cơ quan phụ trách hệ thống này cho biết: mỗi đơn vị hành chính nhận được thông tin lần đầu tiên sau thời gian bao lâu khi nó được ban hành từ kinh thành? Một vấn đề thực sự không đơn giản! Yêu cầu: Cho biết hệ thống truyền tin, thời gian truyền tin giữa hai đơn vị trong hệ thống. Xác định thời gian nhận được thông tin sớm nhất của mỗi đơn vị hành chính tính từ khi thông tin được truyền đi từ kinh thành. Dữ liệu vào: Cho trong file : - Dòng đầu ghi hai số N và M (N<10000, M<100000). - M dòng sau, mỗi dòng chứa ba số nguyên dương i j t với ý nghĩa: đơn vị j có trong danh sách truyền tin của đơn vị i và thời gian truyền tin từ i đến j là t (t < 104). Dữ liệu ra: Ghi ra file : N số nguyên dương, trên dòng thứ k là thời gian để lần đầu tiên đơn vị thứ k nhận được thông tin. Ví dụ: 57 123 131 256 157 321 342 452 0 2 1 3 5 (60% test có M < 1000) ---------------------Hết--------------------- .Hä vµ tªn thÝ sinh Sè bo danh:. Ch÷ kÝ cña gim thÞ 1 Ch÷ kÝ cña gim thÞ 2 const fi = ''; fo = 'subse

• Sáng kiến kinh nghiệm