intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

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

Chia sẻ: Tư Khấu Quân Tường | Ngày: | Loại File: PDF | Số trang:5

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

Đề 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!

Chủ đề:
Lưu

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

  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 chương trình d li u k t qu cho m i test 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
  2. 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 4 3 6 1 4 2 5 3 6 4 6 4 5 5 6 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
  3. 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 2 4 2 1 2 1 2 1 1 1 0 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
  4. 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 1 3 2FFF1 -1 1 4FFF8 1 -1 04FF1 4 -1 3 0 Trang 4/4 Kh i Siêu cúp - 2008
  5. 4 1 2 3 -------------- H T ------------------ Trang 5/4 Kh i Siêu cúp - 2008
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
15=>0