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

Chia sẻ: Nguyen Minh Duc | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu

193
lượt xem 26
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề 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â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 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 56 Bài 2. B n ñ Hapmap Th 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ư t b 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áp ch 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ìm hi 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 ñòi h 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ác d 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 Genotype G 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à chi phí, 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. Tuy nhiê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 - 2008
Ht2) 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 b n HAPMAP.OUT s nguyên dương p là l c lư ng c a t p các Haplotype tìm ñư c. Ví d : HAPMAP.INP HAPMAP.OUT 24 2 1212 1110 Bài 3. Phá bom mìn ð chu n b xây d ng m t khu công nghi p m i, công binh ñư c giao nhi m v rà soát bom mìn có th còn sót l i trên di n tích xây d ng. Khu ñ t có d ng m t hình ch nh t v i t a ñ c a ñ nh trên trái là (a, b) và t a ñ c a ñ nh dư i ph i là (c, d). Các t a ñ ñ u là s nguyên. Bư c ñ u ngư i ta s vô hi u hóa các bom mìn t trư ng t ng khu v c trên m nh ñ t, sau ñó m i ti n hành phá bom mìn thông thư ng. ð làm ñư c vi c ñó công binh s xác ñ nh m t s ñi m ch t m t s ñi m có t a ñ nguyên, ñào ñư ng hào nh và sâu n i các ñi m ch t v i nhau, t o thành m t ñư ng khép kín không t c t bao quanh khu v c nghi v n ch a bom mìn. M i ño n c a ñư ng hào là m t ñư ng th ng ch y song song v i tr c t a ñ ho c song song v i m t trong hai ñư ng th ng x+y=0 hay x−y=0. Sau ñó ngư i ta r i cáp ñi n xu ng ñư ng hào, cho m t dòng ñi n m nh ch y qua. Dòng ñi n s t o ra ñi n trư ng m nh ñ kích n t t c bom mìn t trư ng vùi sâu trong ñ t vùng ñư c ñư ng hào vây quanh. B ph n phá bom mìn t trư ng bàn giao l i cho b ph n phá bom mìn thông thư ng thông tin v công vi c ñã làm bao g m s ñi m ch t và t a ñ các ñi m ñó. Các ñi m ch t ñư c li t kê theo th t ñi vòng quanh chúng theo m t chi u nào ñó. V i các thông tin nh n ñư c ngư i ta in b n ñ khu công nghi p dư i d ng lư i ô vuông kích thư c (c-a)×(b-d), b t ñ u t ô trên trái, t trái sang ph i, t trên xu ng dư i. M i dòng c a lư i ô vuông tương ng v i m t xâu ký t d dài (c-a). M i ô vuông ñơn v trên b n ñ có th có m t trong sáu tr ng thái ñư c ghi nh n b ng m t trong sáu ký t 0, 1, 2, 3, 4, F ph thu c vào m c ñ x lý. Hình 1 cho bi t cách ñánh d u các ô. Ph n g ch chéo xác ñ nh di n tích ñã làm s ch bom mìn t trư ng. Trang 3/4 Kh i Siêu cúp - 2008
Ví d : Khu công nghi p ñư c xác ñ nh b i các t a ñ ñ nh trên trái (-1,3) và ñ nh dư i ph i (4,-1). Có 7 ñi m ch t v i các t a ñ l n lư t là (1, 3), (-1, 1), (1, -1), (4,-1), (3, 0), (4, 1) và (2, 3) (xem hình 2). B n ñ in ra s có d ng: 02F10 2FFF1 4FFF8 04FF1 Yêu c u: Cho bi t a, b, c, d, s ñi m ch t n, t a ñ (xi, yi) c a ñi m ch t th i (i = 1,…, n). Hãy in b n ñ khu công nghi p. D li u: Vào t file văn b n BOMBSAFE.INP: Dòng th nh t ch a 5 s nguyên a, b, c, d và n. • Dòng th i trong n dòng ti p theo ch a 2 s nguyên xi và yi (a ≤ xi ≤ c, d ≤ yi ≤ b). • Các s trên cùng m t dòng ñư c ghi cách nhau m t d u cách. H n ch : (|a|, |b|, |c|, |d| ≤ 200; a < c; d < b; 3 ≤ n ≤ 100). K t qu : ðưa ra file văn b n BOMBSAFE.OUT b n ñ khu công nghi p theo ñúng khuôn d ng ñã mô t . Ví d : BOMBSAFE.INP BOMBSAFE.OUT -1 3 4 -1 7 02F10 13 2FFF1 -1 1 4FFF8 1 -1 04FF1 4 -1 30 Trang 4/4 Kh i Siêu cúp - 2008
41 23 -------------- H T ------------------ Trang 5/4 Kh i Siêu cúp - 2008