Olympic lập trình

Tài liệu tham khảo chuyên ngành công nghệ thông tin - Olympic lập trình. Olympic Tin học Quốc tế (International Olympiad in Informatics - IOI) là một kỳ thi tin học được tổ chức hàng năm dành cho học sinh trung học (độ tuổi tương đương với học sinh lớp 11 và 12 ở Việt Nam). Kỳ thi IOI đầu tiên được tổ chức vào năm 1989.
Nội dung trích xuất từ tài liệu:
Olympic lập trìnhVIETBOOK Olimpic lËp tr×nh I.1. C¸c bµi to¸n Olimpic Trong Olimpic Tin häc Mat-Xc¬-va, ng−êi ta ra cho häc sinh phæ th«ng mét sè nhãm bµi to¸n. Sèc¸c bµi to¸n dao ®éng tõ 5 ®Õn 11 bµi. C¸c bµi to¸n lu«n lu«n cã møc ®iÓm kh¸c nhau, xÕp theo trËt tù dÔdÇn vµ khi tÝnh ®iÓm chØ lÊy 3 lêi gi¶i tèt nhÊt. C¸c thÝ sinh ®−îc b¸o tr−íc tÊt c¶ nh÷ng ®iÒu nµy. Nh÷ng bµi®Çu tiªn cã thÓ lµ kh¸ khã, cßn nh÷ng bµi cuèi cïng mang tÝnh chÊt khÝch lÖ. Kú thi kÐo dµi 4 giê, lêi gi¶i cãthÓ viÕt trªn bÊt kú ng«n ng÷ nµo. Tr−íc khi gi¶i nhÊt thiÕt ph¶i viÕt thuËt gi¶i b»ng lêi. §iÒu nµy lµm choviÖc ®äc ch−¬ng tr×nh dÔ dµng. TÝnh râ rµng cña thuËt to¸n, viÖc tiÕt kiÖm sè c¸c thao t¸c, tÝnh ng¾n gän cñach−¬ng tr×nh ®−îc cho thªm ®iÓm, cßn viÖc lËp tr×nh sö dông m¶ng thõa vµ cã lçi bÞ h¹ thÊp ®iÓm. Trong ph¸t biÓu c¸c bµi to¸n vµ tr×nh bµy thuËt to¸n qui −íc dïng c¸c ký hiÖu sau ®©y: C¸c m¶ng A1,A2,..An ®−îc ký hiÖu lµ A[1:n] víi A[i] lµ c¸c phÇn tö cña nã. Còng nh− vËy kÝ hiÖu A[1:m,1:n] vµ A[i,j]cho m¶ng hai chiÒu..v.v... Sè l−îng c¸c phÇn tö cña m¶ng vµ chØ sè c¸c phÇn tö cña m¶ng lµ c¸c sè tù nhiªn, cßn l¹i lµ c¸c sèthùc ( nghÜa lµ sè víi dÊu phÈy ®éng), nÕu kh«ng cã −íc ®Þnh nµo kh¸c. NÕu ë ®Çu bµi nãi r»ng “ Cho m¶ng A[1:n] th× häc sinh cÇn viÕt ch−¬ng tr×nh tù nhËp sè n, t¹o m¶ngn phÇn tö vµ nhËp gi¸ trÞ cña c¸c phÇn tö nµy. NÕu trong ng«n ng÷ ( VÝ dô ng«n ng÷ Pascal...) kh«ng cãm¶ng ®éng, th× cÇn chÊp nhËn nVIETBOOK80.2.2 Tæng b×nh ph−¬ng Cã thÓ viÕt sè tù nhiªn M cho tr−íc d−íi d¹ng tæng c¸c b×nh ph−¬ng cña hai sè tù nhiªn hay kh«ng ?H·y viÕt ch−¬ng tr×nh gi¶i bµi to¸n nµy.80.2.3 C¸c sè kh¸c nhau Cho tr−íc m¶ng sè A[1:m]. T×m vµ in ra sè c¸c sè kh¸c nhau trong m¶ng nµy. VÝ dô trong m¶ng 5,7,5 cã hai sè kh¸c nhau ( 5 vµ 7 ).80.3.1 Sè cã tæng c¸c ch÷ sè cho tr−íc ViÕt ch−¬ng tr×nh in ra tÊt c¶ c¸c sè ë hÖ c¬ sè 10 cã ba ch÷ sè mµ tæng c¸c ch÷ sè b»ng mét sè tùnhiªn cho tr−íc.80.3.2 M + 1 ë hÖ nhÞ ph©n Sè nguyªn kh«ng ©m M ®−îc cho bëi m¶ng c¸c ch÷ sè nhÞ ph©n lµ a0, a1, a2,...an-1 : M = an- n-1.21 +......+ a1.2 + a0Trong ®ã ai b»ng 0 hoÆc 1 ( i = 0,1,2,...n-1 ) H·y viÕt m¶ng c¸c ch÷ sè nhÞ ph©n cña M+1.80.3.3 Cùc ®¹i cña c¸c cùc tiÓu : Trong m¶ng X[1:m,1:n] tÊt c¶ c¸c sè kh¸c nhau. ë mçi dßng t×m mét phÇn tö nhá nhÊt, sau ®ã trongsè nµy chän ra sè lín nhÊt. H·y in ra chØ sè cña dßng cña m¶ng X chøa sè ®· ®−îc chän.80.3.4. Ho¸n vÞ 0, 1, 2.Trong m¶ng X[1:n] mçi phÇn tö b»ng 0, 1 hoÆc 2. Ho¸n vÞ c¸c phÇn tö cña m¶ng, sao cho ®Çu m¶ng chøac¸c sè 0, sau ®ã lµ c¸c sè 1 vµ cuèi m¶ng lµ c¸c sè 2 ( kh«ng ®−îc dïng m¶ng phô ). Olimpic 81 C¸c thÝ sinh ®−îc giao 5 bµi to¸n s¾p xÕp theo thø tù dÔ dÇn. ChØ ®−îc tÝnh ®iÓm 3 bµi.81.1 Hµm sè : Hµm sè f(n) víi c¸c sè n nguyªn kh«ng ©m ®−îc x¸c ®Þnh nh− sau :f(0) = 0 , f(1) = 1 , f(2n)= f(n) , f(2n+1) = f(n) + f(n+1). Víi N cho tr−íc x¸c ®Þnh vµ in ra f(N).§iÒu kiÖn b¾t buéc : N ®ñ lín ®Ó kh«ng thÓ m¶ng gåm N phÇn tö ( hoÆc khai b¸o m¶ng cã chiÒu dµi t¨ngtheo N ).81.2. CÆp bèn sè . H·y n¹p sè n vµ lÊp ®Çy m¶ng hai chiÒu kÝch th−íc n2 b»ng c¸c sè 1, 2, 3,.. theo h×nh xo¾n èc (h×nh vÏ ).81.3. C¸c sè lËp tõ c¸c ch÷ sè kh¸c nhau: In ra tÊt c¶ c¸c sè tù nhiªn cã 4 ch÷ sè mµ biÓu diÔn ë hÖ thËp ph©n cña chóng kh«ng cã hai ch÷ sènµo gièng nhau.81.5 Lo¹t c¸c sè kh«ng. Trang 2VIETBOOK Cho m¶ng sè A[1:n] . H·y t×m ®é dµi cña d·y con lín nhÊt gåm c¸c phÇn tö liªn tiÕp toµn sè kh«ng. Olimpic 82 C¸c thÝ sinh ®−îc giao 6 bµi to¸n theo trËt tù dÔ dÇn. ChØ tÝnh ®iÓm 3 bµi.82.1 H×nh ch÷ nhËt . Trªn giÊy kÎ « khæ 100 x 100 «, cã vÏ mét sè h×nh ch÷ nhËt. Mçi h×nh ch÷ nhËt ®−îc t¹o tõ c¸c «nguyªn vÑn, c¸c h×nh kh¸c nhau kh«ng chång lªn nhau vµ kh«ng tiÕp xóc nhau. ( h×nh 1.2 ) Cho m¶ng kÝch th−íc 100 x 100, trong ®ã phÇn tö A[i,j] = 1 nÕu « [i,j] thuéc mét h×nh ch÷ nhËt nµo®ã, cßn A[i,j] = 0 trong tr−êng hîp ng−îc l¹i. H·y viÕt ch−¬ng tr×nh tÝnh vµ in ra sè c¸c h×nh ch÷ nhËt.82.2 C¸c ph©n sè ®−îc s¾p thø tù In theo trËt tù t¨ng dÇn tÊt c¶ c¸c ph©n sè tèi gi¶n trong kho¶ng (0, 1) cã c¸c mÉu sè kh«ng v−ît qu¸7.82.3 Tæng theo tËp con : Cho tr−íc m¶ng sè nguyªn A[1: n] vµ sè M . T×m tËp hîp c¸c phÇn tö A[i1], A[i2], ......A[ik] 1VIETBOOK Olimpic 83 C¸c thÝ sinh ®−îc giao 5 bµi theo trËt tù dÔ dÇn. ChØ cã 3 bµi ®−îc tÝnh ®iÓm.83.1. §¶o bit : Sè nguyªn m ®−îc viÕt trong hÖ c¬ sè 2 theo trËt tù ng−îc l¹i. Sè nhËn ®−îc viÕt trong hÖ thËp ph©n,®−îc coi lµ gi¸ trÞ cña hµm B(m). H·y in gi¸ trÞ B(m) víi m=512,513,514,...1023.ThÝ dô, ba gi¸ trÞ ®Çu tiªn cÇn in lµ : 1; 513; 257;...83.2. H×nh tam gi¸c vµ ®iÓm : Cho tr−íc trong hÖ to¹ ®é vu«ng gãc c¸c ®iÓm (X1,Y1), (X2,Y2),(X3,Y3) lµ ®Ønh cña mét tam gi¸c vµX,Y lµ to¹ ®é cña mét ®iÓm. H·y x¸c ®Þnh xem ®iÓm ®ã cã n»m trong tam gi¸c hay kh«ng ( bá qua sai sècña phÐp tÝnh)83.3. Mª cung : Du kh¸ch cã thÓ ra khái mª cung ®−îc hay kh«ng ? NÕu cã thÓ h·y in ®−êng ®i tõ lèi ra ®Õn vÞ trÝ ban®Çu cña du kh¸ch. Mª cung ®−îc cho bëi m¶ng A kÝch th−íc 40 x 40, trong ®ã : A[k,m] = 0 , nÕu « [k,m] ®i qua ®−îc (« th«ng) A[k,m] = 1 , nÕu « [k,m] kh«ng ®i qua ®−îc (« cÊm).VÞ trÝ ban ®Çu cña du kh¸ch ®−îc cho ë « th«ng [i,j]. Du kh¸ch cã thÓ chuyÓn tõ mét « th«ng nµy ®Õn «th«ng kh¸c ...