- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Príklady 1. kola zimnej časti 22. ročníka KSP
Milé naše riešiteľky, mílí naši riešitelia,
srdečne vás pozývame riešiť ďaľší ročník KSP. Aj napriek tomu, že už nie ste nováčikovia, bolo by dobré, aby ste si aspoň akože prečítali pravidlá. Pretože najviac bodov získajú tí, čo sa nimi budú riadiť. Najlepší z vás budú na jar pozvaní na sústredenie, takže sa ponáhľajte a posielajte nám vaše riešenia do 8. novembra 2004. K riešeniam nezabudnite priložit známky v hodnote 15,-Sk.
KSPáci
- Ohne na Kapingamarangi
- O Semaforovej rally Kocúrkovo 2004
- O papagájoch
- O hre Scrobbli
- Ovez fmtkojgjbdz
1. Ohne na Kapingamarangi
(15 bodov)
Ostrovy Kapingamarangi sú rozmiestnené dosť zvláštne. Tvoria obdĺžnik zložený z N radov po M ostrovoch. Z neznámych príčin ich niekto pooznačoval zo severu na juh a zo západu na východ súradnicami [1, 1] až [N, M]. V strede každého ostrova sa nachádza veľké ohnisko, od ktorého závisí život ľudí na ostrove. Podľa zlej kliatby totiž môže na každom ostrove horieť najviac jeden oheň, a preto môžu ľudia variť len na jednom mieste na ostrove. Zlá kliatba však má dodatok, že keď niekto zapáli alebo zahasí oheň (teda oheň zmení svoj stav) na ostrove so súradnicou [i, j], aj ohne na ostrovoch v obdĺžniku s ľavým horným rohom na tomto ostrove a pravým dolným rohom na ostrove [N, M] zmenia svoj stav.
Ešte prednedávnom horeli všetky ohne a nikto nevedel o zlej kliatbe. No keď sa požiarnici na ostrove Nuoruko rozhodli, že budú trénovať hasenie na jedinom ohni na ostrove, začali sa veľké nepokoje. Na ďalších ostrovoch sa ohne zhasli tiež, čo vyvolalo sériu zapaľovaní ohňov. Na niektorých ostrovoch sa v súčasnosti oheň zapaľuje a zhasína v pravidelných 10-sekundových intervaloch.
Panovník Kapingamarangi sa rozhodol situáciu riešiť. Keďže sa dozvedel o zlej kliatbe, chce dať všetko do pôvodného stavu. Zakázal komukoľvek zapaľovať alebo zahášať oheň a požiadal vás, aby ste mu poradili, ako pozapaľovať ohne na všetkých ostrovoch na čo najmenej krokov.
Úloha
Sú dané kladné celé čísla N a M a mapa ohňov. Mapu tvorí N riadkov po M stĺpcoch núl alebo jednotiek. Nula predstavuje zahasený oheň, jednotka zapálený oheň.
Zmena stavu ohňa na ostrove so súradnicou [i, j] spôsobí zmenu stavu všetkých ohňov na ostrovoch v obdĺžniku s ľavým horným rohom [i, j] a pravým dolným rohom [N, M]. Úlohou je zistiť najmenší počet zmien potrebných na to, aby horeli všetky ohne.
Príklad
Vstup
N=3, M=4
1 0 1 1
1 0 0 1
0 1 0 1
Výstup
6
(Napr. postupne zmeníme stav ohňa na [1,2], [3,1], [1,3], [2,3], [3,3] a [2,4].)
2. O Semaforovej rally Kocúrkovo 2004
(15 bodov)
Dámy a páni, páni a dámy! Vitajte na preslávenej Semaforovej rally Kocúrkovo 2004! Iba tu v Kocúrkove môžete sledovať tento skvost ducha a sami okúsiť vzrušenie, ktoré vám neponúkne ani bratislavská MHD! Stante sa priamymi účastníkmi exhibície a súťažte po boku takých velikánov akými sú Rejdi Burner, Maestro Kewo alebo Topless Tono!!! Neváhajte a vyneste aj vaše meno medzi hviezdy!
Úloha
Na vstupe je kladné celé číslo N---počet križovatiek a kladné celé číslo M---počet ulíc medzi nimi. Ďalej nasleduje riadok s dvoma kladnými celými číslami b a e, ktoré hovoria, v ktorej križovatke je začiatok a v ktorej cieľ cesty. Po tomto riadku nasleduje M riadkov s trojicami čísel i, j a k, ktoré znamenajú, že križovatka i je spojená s križovatkou j a prejdenie medzi nimi trvá čas k. Ďalej nasleduje ďaľších N riadkov s kladnými celými číslami ci, pričom číslo ci predstavuje periódu, v ktorej sa mení farba i-teho semaforu.
Kocúrkovské semafory fungujú nasledovne: Na každej križovatke je práve jeden semafor. Keď svieti červená, nemôže do križovatky vôjsť nik. Naopak, keď svieti zelená, môžu do nej vôjsť a prejsť ňou autá zo všetkých prichádzajúcich ulíc. Kocúrkovčanom zjavne uniklo, načo je vlastne semafor dobrý. Ale tak už to v Kocúrkove chodí.
Na začiatku svietia všetky semafory na zeleno. Potom po prejdení ci času sa zmení farba na i-tom semafore na červenú a potom, znovu po prejdení času ci sa farba semaforu i zmení na zeleno.
Vašou úlohou je nájsť takú cestu samozrejme treba dodržiavať dopravné predpisy zo začiatočnej križovatky b do koncovej e, po ktorej bude cesta trvať najkratšie. Vypíšte poradie križovatiek ako máte ísť, aby ste sa najrýchlejšie dostali do koncovej križovatky. Stav semafóru v koncovej križovatke už vo výpočte neuvažujte. Pokiaľ je takýchto riešení viac, vyberte si ľubovoľné.
Príklad
Vstup
4 5
1 4
1 2 1
1 3 3
2 4 5
3 4 2
2 3 7
1
3
2
6
Výstup
1 2 4
(V križovatke 1 nečakáme a rovno ideme do križovatky 2, táto cesta trvá čas 1. Na križovatke 2 svieti stále zelená a tak pokračujeme ďalej ulicou na križovatku 4 a cesta nám bude trvať dokopy 6. Keby sme išli cestou 1 3 4, budeme mať rovnaký výsledok: Pôjdeme z križovatky 1 na križovatku 3, to nám bude trvať čas 3, tu budeme stáť na červenej. Zelená naskočí na križovatke 2 v čase 4, kedy sa vyberieme na križovatku 4, kam sa dostaneme za čas 2 a teda výsledný čas bude tiež 6.)
3. O papagájoch
(15 bodov)
Bolo raz jedno kráľovstvo, kde bolo príliš veľa krotkých spotených papagájov. Skrotili ich dávni králi a dnes už nikto nevie načo. Legenda hovorí, že pomohli v bitke proti zlému čarodejníkovi Grupostanxovi. Každopádne, teraz iba poskakujú po meste a každému lezú na nervy. Došlo to až tak ďaleko, že kráľovná prikázala zriadiť špeciálny inštitút na vyriešenie problému krotkých spotených papagájov (ŠIVPKSP). Vedci v ŠIVPKSP sa dlho snažili nájsť prostriedok, ktorým by papagájov z kráľovstva vyhnali a konečne to vyzerá, že svitá na lepšie časy. Vedec menom Stamolangax prišiel s objavom, že všetky dnešné papagáje pochádzajú zo spoločného prapapagája. Skúšal robiť pokusy s papagájmi a zistil, že ak povie vhodný palindróm slovo, ktoré sa odpredu číta rovnako ako odzadu -- napr. "oko" alebo "radar" vytvorený z mena prapapagája, tak sa papagáj jednoducho začne nekontrolovateľne smiať a odskáče do teplých krajín. Lenže problém je, že neexistuje univerzálne slovo, ktoré treba papagájom povedať, niektoré reagujú na iné palindrómy ako iné papagáje. Dokonca rozdielne reagujú aj na palindrómy, ktoré znejú síce rovnako, ale boli z mena prapapagája inak vytvorené. Preto potrebujú vedci z ŠIVPKSP vašu pomoc, aby zistili koľko palindrómov sa dá z mena prapapagája vytvoriť...
Úloha
Na vstupe je zadané meno prapapagája zložené z malých písmen anglickej abecedy. Úlohou je vypísať koľkými spôsobmi sa z neho dá vyškrtať niekoľko (aj nula) písmen tak, aby sme dostali palindróm. Nezáleží na poradí vyškrtávania, t.j. spôsoby, ktoré sa líšia len poradím vyškrtávania, považujeme za rovnaké. Slovo zložené z nula písmen nie je palindróm.
Príklad
Vstup
aba
kalbal
Výstup
5
12
(Zo slova aba palindróm vytvoriť tak, že vyškrtneme 1. a 2. písmenko, alebo 1. a 3., alebo 2. a 3., alebo 2., alebo žiadne. Preto je odpoveď 5. Všimnite si, že v prvom a treťom prípade dostaneme ten istý palindróm, ale vyškrtnutím iných písmen.)
4. O hre Scrobbli
(15 bodov)
Scrobbli je spoločenská hra, ku ktorej máte pribalenú hraciu dosku, písmenká a vrecúško, z ktorého sa písmenká vyťahujú. V každom kole si hráč vytiahne vopred daný počet písmeniek. Úlohou je z písmeniek zostrojiť čo najviac slov, ktoré sú v Slovníku zmysluplných slov. Miško sa rozhodol, že bude trošku podvádzať, takže použije program, ktorý mu bude všetky vhodné slová vyhľadávať. Pomôžte mu napísať takýto program.
Úloha
Sú dané kladné čísla N, K a M---počet slov v slovníku, počet písmen a počet kôl. Ďalej je daný slovník (N K-písmenových reťazcov) a M K-písmenových reťazcov písmen, ktoré si Miško vytiahol. Napíšte program, ktorý pre každý reťazec vypíše všetky slová zo slovníka, ktoré vzniknú poprehadzovaním písmen v reťazci.
Príklad
Vstup
N=12, K=5, M=3
slovník:
halda,
letmo,
otlak,
malta,
kniha,
torta,
mleto,
tlama,
motor,
modla,
motel,
dlaha
písmená:
dalha,
matal,
omlet
Výstup
halda
dlaha
malta
tlama
motel
letmo
mleto
5. Ovez fmtkojgjbdz
(15 bodov)
V Národnej banke Svazijska mali donedávna velikánsky starý trezor, v ktorom bola kopa diamantov. Týmito diamantmi sú samozrejme kryté svazijské bankovky. Do trezoru mali prístup len členovia správnej rady NBS. Ale to nebolo len tak. Keďže ani členovia správnej rady si navzájom príliš neverili, vyriešili to tak, že dvere trezoru ovešali kopou zámkov a vhodne si od nich rozdali kľúče. Výsledkom bolo, že do trezoru mohli vstúpiť len vtedy, ak spomedzi všetkých siedmich členov boli prítomní aspoň štyria.
Nepovinná domáca úloha: Koľko najmenej zámkov na to bolo treba a ako rozdať kľúče?
Problémy nastali minulý štvrtok, keď svazijská vláda s okamžitou platnosťou schválila novelu zákona o ochrane diamantov. NBS musela zväčšiť počet členov správnej rady a navyše kúpiť nový namakaný digitálny trezor. Ale beda, na nový trezor sa zámky namontovať nedali. Otvoril sa len vtedy, keď sa mu na klávesnici zadalo správne heslo -- jedno číslo z daného rozsahu.
Keď posledný pokus o namontovanie zámkov zlyhal, rozhodli sa technici NBS prečítať si manuál. K trezoru bola priložená útla knižka, ktorá všetko potrebné vysvetlila:
Nech má správna rada N členov a nech na otvorenie trezoru treba ľubovoľných K z nich. Očíslujme členov správnej rady od 1 do N. Heslom je číslo z rozsahu od 0 do P-1 (kde P je prvočíslo väčšie ako N).
Keď sa uzavrú dvere trezoru, ten si náhodne vygeneruje heslo h. Následne si ešte vygeneruje K-1 celých čísel a1, ..., a(K-1) (tiež z rozsahu od 0 do P-1). Všimnime si teraz nasledovný polynóm:
f(x) = a(K-1) x(K-1) + ... + a2 x2 + a1 x + h
Zjavne f(0)=h. Trezor oznámi i-temu členovi správnej rady jeho poradové číslo i a hodnotu ti = f(i) mod P.
Úloha
a) Ukážte, že keď sa stretne aspoň K členov správnej rady, vedia jednoznačne vypočítať heslo h.
b) Ukážte, že keď sa stretne menej ako K členov správnej rady, nevedia o hesle h povedať vôbec nič -- teda že pri tom, čo vedia, každé číslo môže byť heslom.
c) Zamyslite sa, aké problémy má tento spôsob zabezpečenia prístupu do trezoru. Čo sa napríklad stane, ak by sa stretlo K členov správnej rady, ale jeden z nich bude chcieť ostatných podviesť?
Možno hint.
Ľahko vieme sčítať, odčítať a násobiť modulo P. (Napríklad ak P=7, tak 4+6=3 a 3*4=5). Ako je to ale s delením? Ku každému celému x nesúdeliteľnému s P existuje y také, že xy dáva po delení P zvyšok 1. (Prečo je tomu tak?) Takéto y voláme inverzný prvok k x a značíme ho x(-1). Ak niekedy potrebujeme deliť číslom x, budeme namiesto toho násobiť číslom x(-1). Presvedčte sa, že takto definované delenie má dostatočne podobné vlastnosti ako klasické delenie reálnych čísel.
© KSP, 2. september 2004, webmaster
