Đề thi olympic tin học sinh viên lần thứ 17 - đề 1

Tham khảo tài liệu đề thi olympic tin học sinh viên lần thứ 17 - đề 1, công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Đề thi olympic tin học sinh viên lần thứ 17 - đề 1 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 cho m i test chương trình d li u k t qu X lý song song PARCOMP.??? PARCOMP.INP PARCOMP.OUT 1 giây B n ñ Hapmap HAPMAP.??? HAPMAP.INP HAPMAP.OUT 1 giây Phá bom mìn BOMBSAFE.??? BOMBSAFE.INP BOMBSAFE.OUT 1 giâyChú ý: 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 songT 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 Ntá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. Tuynhiê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 ítnh 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 igian 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 - 2008D li u: Vào t file văn b n PARCOMP.INP: 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 PARCOMP.OUT hai s T và P tìm ñư c.Ví d : PARCOMP.INP PARCOMP.OUT 10 43 6 14 25 36 46 45 56Bài 2. B n ñ HapmapTh k XXI ñư c coi là th k c a công ngh thông tin và công ngh sinh h c. S phát tri n vư tb c c a công ngh sinh h c ñã nâng cao ch t lư ng cu c s ng cũng như tìm ra các phương phápch a b nh m i. M c dù b n ñ gen c a con ngư i ñã ñư c gi i mã t năm 2001, vi c phân tích tìmhi u n i dung c a b n ñ gen là m t công vi c ph c t p ñang ñư c ti n hành. Công vi c này ñòih i k t h p các phương pháp tính toán c a khoa h c máy tính, xác su t th ng kê ñ phân tích cácd li u sinh h c. M t trong s nh ng bài toán ñang r t ñư c quan tâm hi n nay là xây d ng b n ñHapmap c a con ngư i ñ giúp vi c ch n ñoán b nh cũng như tìm ra các lo i thu c ch a tr m i.Trong xây d ng b n ñ Hapmap, Haplotype và Genotype là hai khái ni m cơ b n trong sinh h cñư c phát bi u ñơn gi n như sau: 1. Haplotype H = (h1,…, hn) là dãy g m n s , trong ñó hi ch nh n giá tr 0 ho c 1. 2. Genotype G = (g1,…, gn) là m t dãy g m n s ñư c t o ra t s ñ i sánh hai Haplotype Hp = (hp1,…,hpn) và Hm = (hm1,…,hmn) theo quy t c sau: gi = 0 n u hpi = hmi = 0; • gi = 1 n u hpi = hmi = 1; • gi = 2 n u hpi ≠ hmi . •Như v y, m i c p Haplotype Hp và Hm ch t o ra m t Genotype G duy nh t, nhưng m t GenotypeG l i có th ñư c t o ra t nhi u c p Haplotype khác nhau. Thông tin v gen c a m t con ngư iñư c xác ñ nh b i m t c p Haplotype. Do h n ch v m t công ngh , cũng như th i gian và chiphí, nên hi n t i chúng ta m i ch có ñư c thông tin cá nhân v Genetype cho m i ngư i. Tuynhiên, ñ ñáp ng m c ñích nghiên c u, chúng ta l i c n gi i mã ñư c thông tin Haplotype (Ht1, Trang 2/4 Kh i Siêu cúp - 2008Ht2) t Genotype Gt cho ngư i t. Do vi c gi i mã là không duy nh t, nên bài toán ñư c ñ t ra nhưsau.Yêu c u: Cho thông tin Genotype là G1,…,Gk c a k ngư i, hãy tìm k c p Haplotype (H11, H12), …,(Hk1, Hk2) tương ng cho k ngư i trên sao cho t p {H11, H12, …, Hk1, Hk2} có l c lư ng là nh nh t.D li u: Vào t file văn b n HAPMAP.INP có c u trúc như sau: Dòng ñ u ghi 2 s k, n (k < 21, n < 50); • Dòng th t trong k dòng ti p theo ch a n s bi u di n Genotype Gt c a ngư i th t. •Các s trên cùng m t dòng ñư c ghi cách nhau m t d u cách.K t qu : Ghi ra file văn ...