tailieunhanh - Đề thi Olympic Tin học sinh viên lần thứ XIX khối Siêu cúp (Năm 2010)

Đề thi Olympic Tin học sinh viên lần thứ XIX khối Siêu cúp (Năm 2010) cung cấp cho thí sinh các bài tập giải quyết vấn đề lập trình gồm: truyền tin; san bằng; mạch in; genome; . Mời các bạn cùng tham khảo chi tiết nội dung đề thi! | OLYMPIC TIN HỌC SINH VIÊN LẦN THỨ XIX 2010 Khối thi Siêu cúp Thời gian làm bài 180 phút Ngày thi 25-11-2010 Nơi thi ĐẠI HỌC CÔNG NGHỆ ĐHQG Hà nội TỔNG QUAN ĐỀ THI Tên file Tên file Tên file Hạn chế thời gian Tên bài chương trình dữ liệu kết quả cho mỗi test Truyền tin COMNET. 1 giây San bằng EVENMAKE. EVENMAKE .INP 2 giây Mạch in CIRCUIT. CIRCUIT .INP 2 giây Genome GENOME. 2 giây Chú ý Dấu được thay thế bởi đuôi ngầm định của ngôn ngữ được sử dụng để cài đặt chương trình. Thí sinh phải nộp cả file mã nguồn của chương trình và file chương trình thực hiện chương trình đã được biên dịch ra file .exe . Hãy lập trình giải các bài sau đây Bài 1. Truyền tin Công ty X lên kế hoạch kết nối n máy tính đang hoạt động trong công ty. Các máy tính được đánh số từ 1 đến n. Theo kế hoạch Công ty lắp đặt m đường truyền tin một chiều để kết nối các máy tính. Các đường truyền tin được đánh số từ 1 tới m. Đường truyền tin thứ i cho phép truyền tin từ máy tính ui tới máy tính vi i 1 2 . m. Các đường truyền tin sẽ được lắp đặt lần lượt theo thứ tự từ 1 tới m. Việc lắp đặt một đường truyền tin mất đúng 1 đơn vị thời gian. Ta nói máy tính s có thể truyền tin tới máy tính t nếu tồn tại một dãy các máy tính s p1 p2 . pk t sao cho có đường truyền tin từ máy tính pi tới máy tính pi 1 i 1 2 . k 1. Trong quá trình lắp đặt đến một thời điểm nào đó máy tính 1 có thể truyền tin đến máy tính n theo những đường truyền tin đã được lắp đặt. Yêu cầu Giả sử việc lắp đặt các đường truyền tin được thực hiện liên tục bắt đầu từ thời điểm 0 hãy tính thời điểm sớm nhất mà máy tính 1 có thể truyền tin tới máy tính n. Dữ liệu Vào từ file văn bản Dòng thứ nhất chứa hai số nguyên dương n m 2 n m 300000 Dòng thứ i trong số m dòng tiếp theo chứa hai số nguyên dương ui vi. Hai số liên tiếp trên một dòng được ghi cách nhau ít nhất một dấu cách. OLP 2010 Đề thi khối Siêu cúp Trang 1 4 Kết quả Ghi ra file văn bản một số nguyên