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

Đề thi Olympic Tin học sinh viên lần thứ XVII khối Siêu cúp (Năm 2008) cung cấp cho thí sinh các bài toán lập trình nhằm giải quyết các vấn đề sau: xử lý song song; bản đồ Hapmap; phá bom mìn; . 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 XVII 2008 Kh i thi Siêu cúp Th i gian làm bài 180 phút Ngày thi 21-11-2008 Nơi thi ð i h c K thu t Công ngh TP. HCM 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 X lý song song PARCOMP. 1 giây B n ñ Hapmap HAPMAP. 1 giây Phá bom mìn BOMBSAFE. 1 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. X lý song song T i th i ñi m 0 m t siêu máy tính có m t s lư ng không h n ch các b x lý nh n th c thi N tác v ñư c ñánh s t 1 ñ n N. M i b x lý có th hoàn thành m t tác v b t kỳ trong 1 giây. Tuy nhiên trên t p các tác v ñã cho có ràng bu c v trình t th c hi n ñư c mô t b i các c p tác v A B cho bi t tác v A ph i ñư c hoàn thành trư c khi tác v B ñư c b t ñ u th c hi n. Yêu c u Hãy tính kho ng th i gian ít nh t T c n thi t ñ hoàn thành t t c các tác v và s lư ng ít nh t P b x lý c n huy ñ ng ñ hoàn thành t t c các tác v trong kho ng th i gian T. Ví d Có N 10 tác v . Có 6 ràng bu c trình t th c hi n các tác v sau đây 1 4 2 5 4 5 3 6 4 6 5 6 . Khi ñó T 4 và s lư ng ít nh t các b x lý c n s d ng ñ hoàn thành t t c các tác v trong th i gian 4 là P 3. B ng sau ñây mô t m t kh năng phân b các b x lý th c hi n các tác v B x lý 1 B x lý 2 B x lý 3 Bư c 1 3 1 2 Bư c 2 4 7 9 Bư c 3 5 8 - Bư c 4 6 10 - Trang 1 4 Kh i Siêu cúp - 2008 D li u Vào t file văn b n Dòng ñ u tiên ch a s lư ng tác v N 1 N 2000 Dòng th hai ch a s nguyên M là s lư ng ràng bu c trình t M i dòng trong s M dòng cu i mô t m t ràng bu c trình t bao g m 2 s nguyên A và B ñư c ghi cách nhau b i d u cách cho bi t tác v A ph i ñư c hoàn thành trư c tác v B. K t qu Ghi ra file văn b n hai s T và P tìm ñư c. Ví d 10 4