- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Príklady 1.kola letnej časti 19.ročníka KSP-Z
Milé naše riešiteľky, mílí naši riešitelia,
dostávajú sa vám do rúk zadania 1. kola letnej časti 19. ročníka KSP-Z. Prečítajte si pozorne propozície súťaže a hor sa riešiť. Svoje riešenia nám posielajte najneskôr do 25. marca. Nezabudnite k nim priložiť známky v hodnote 15,- Sk.
KSPáci
1. Zanzibarské jednosmerky
Zanzibar je veľké a prastaré mesto. Začali ho stavať ešte pred našim letopočtom. Začiatkom letopočtu však naši prapredkovia nemali ani kúsok citu a pochopenia pre modernú urbanizáciu, automobilovú dopravu, potreby dnešného moderného človeka a vôbec. Zaoberali sa hlavne tým, ako na čo najmenšiu plochu nadžgať čo najviac chatrčí. Žiaľ, týmto vývojom sa stalo, že uličky v Zanzibare sú priveľmi úzke pre obojsmernú automobilovú dopravu.
Začiatkom 21. storočia sa problém vyostril natoľko, že mestská rada bola nútená narýchlo zaviesť v meste systém jednosmeriek. Zbastlená reforma však, zdá sa, všetko iba zhoršila. Zapeklitým problémom totiž ostáva, či sa v meste dá dostať autom z ľubovoľného miesta na ľubovoľné iné tak, aby sa dodržal predpísaný smer jazdy. Zistite, či je to skutočne tak!
Úloha
Zanzibar si možno predstaviť ako systém jednosmeriek, ktoré vedú medzi križovatkami. Zadané je N - počet križovatiek a M - počet jednosmeriek. Ďalej je daných M jednosmeriek. Jednosmerka je daná ako dvojica čísel križovatiek x,y (1 <= x,y <= N), medzi ktorými vedie. Jazdiť sa smie po tejto ulici len v smere od križovatky x ku križovatke y. Napíšte program, ktorý zistí, či sa možno medzi dvoma ľubovoľnými križovatkami v meste dostať autom tak, aby sme dodržali dopravné predpisy.
Príklad
Vstup
N=6, M=7
1 2
2 3
3 1
4 5
5 6
6 4
1 4
Výstup
Nie, nedá sa dostať medzi ľubovoľnými dvoma križovatkami.
(Pozn.: napríklad sa nedá dostať z križovatky 5 na križovatku 3)
2. Zábudliví trpaslíci
"A čo si nám to chcel povedať?", pýtali sa (už trochu nahnevaní, pretože sa to pýtajú už siedmy krát) trpaslíci chudáka Zedrika. No nestávalo sa to len jemu, ale viacerým trpaslíkom - niekedy, keď si dohodli stretnutie pod jedným zo stromčekov, si zrazu nemohli podaktorí spomenúť, čo chceli ostatným povedať. Jednoducho - trpasličia skleróza. Nebola to choroba nebezpečná, ale tiež nie veľmi príjemná. Každý trpaslík mal doma na chladničke lístok, kam si písal všetky dôležité veci, aby na ne nezabudol. No keď išiel na stretnutie pod stromček, chladničku si so sebou pochopiteľne nebral, a potom sa mohlo stať, že kým prišiel k stromčeku, zabudol, čo vlastne chcel.
Preto sa rada starších rozhodla, že s tým treba niečo spraviť. Ideálne zjavne bude, ak sa budú stretávať pod takým stromčekom, aby všetci trpaslíci spolu prešli čo najmenšiu vzdialenosť. (vtedy totiž (spolu) zabudnú najmenej - čím ďalej musí trpaslík zájsť, tým viac toho zabudne) Trpasličia dedinka má len jednu ulicu, na ktorej sú domčeky trpaslíkov. Medzi každými dvoma domčekmi rastie stromček, pod ktorým sa dá stretávať. Polohy domčekov, ako aj stromčekov, sú celé čísla, ktoré určujú vzdialenosť daného objektu od začiatku ulice.
Úloha
Pomôžte rade starších a napíšte im program, ktorý im povie, kde sa majú trpaslíci stretnúť, aby toho spolu čo najmenej prešli (a čo najmenej zabudli). Vstupom programu sú utriedené pozície N domčekov, z ktorých z každého pôjde na miesto stretnutia jeden trpaslík, a ďalej utriedené pozície N-1 stromčekov - jeden medzi susednými dvoma domčekmi. Program má za úlohu zistiť, pri ktorom zo stromčekov sa majú trpaslíci stretnúť.
Príklad
Vstup
N=5
domčeky: 0, 3, 10, 12, 16
stromčeky: 1, 6, 11, 13
Výstup
Najmenej sa nachodia, ak sa stretnú pri stromčeku na pozícii 11.
3. Z
Iste ste si všimli, že svetu v poslednej dobe nehrozila žiadna zničujúca katastrofa ako napr. mimozemšťania, či neposlušné asteroidy. Toto teda výskumníci z NASA nemohli nechať len tak. Zvolali preto všetky kockaté mozgy, čo sa dali kúpiť a poďho na to.
Čo nikto načakal (ale my hej... :-), Sergejovi sa podarilo odhaliť separatistickú skupinu banditov, ktorej každý člen je označený štvorcom nejakého (vždy iného) prirodzeného čísla i (kde i=1,2,...). Keď sa títo banditi stretnú naraz na ulici, usporiadajú sa automaticky vzostupne podľa hodnoty svojich označení, takže tvoria nekonečný rad nejakým spôsobom sa striedajúcich cifier 0-9.
Keď sa už raz banditom podarí usporiadať sa, v priebehu niekoľkých okamihov sa dohodnú, na ktorom mieste v našom nekonečnom rade bude umiestnená zbraň Z, ktorá všetkých ľudí premení na kocky. Sergej je hlavička, a tak vám dokáže veľmi rýchlo zistiť a poskytnúť informáciu o mieste, na ktorom ukryli banditi zbraň (to vysleduje z ich správania - obyčajná psychológia). Ako však rýchlo a ľahko zistiť kód na odstavenie zbrane? Samozrejme tak, že zistíte, aká cifra sa na Sergejom určenom mieste nachádza. Tipovať nemôžete, máte len jeden pokus.
Uvedomte si, že oči celého sveta sa upierajú na vás!
Úloha
Ak napíšeme za seba štvorce prirodzených čísel 1...nekonecno, dostaneme rad zložený z cifier 0-9. Na vstupe je číslo k. Vašou úlohou je vytvoriť algoritmus, ktorý nájde cifru na k-tom mieste v tomto rade.
Príklad
Vstup
k=13
Výstup
4
(Pozn.: rad sa začína 149162536496481...)
4. Záhady Kiribatského rybolovu
Kiribatská vláda sa rozhodla zvýšiť príjmy štátu zavedením povolení na rybolov. Povolenia sa udeľujú nasledovne: Mapa Kiribati (ako isto viete) je rozdelená na MxN štvorcov. Pre potreby udeľovania povolení je každý z týchto štvorcov prehlásený buď za pevninu, alebo za more. Za 10 kiribatských bubákov môže ľubovoľný občan požiadať o povolenie na rybolov. Do žiadosti musí uviesť časť mapy, pre ktorú má toto povolenie platiť. Táto časť musí byť obdĺžnikového (resp. štvorcového) tvaru a má byť tvorená práve niekoľkými štvorcami mapy. Každá takáto oblasť je teda jednoznačne určená súradnicami štvorcov mapy v dvoch jej protiľahlých rohoch. Povolenie je občanovi udelené práve vtedy, keď oblasť, ktorú vyplnil do žiadosti, obsahuje iba more.
Väčšina Kiribatčanov rada loví ryby. Na druhej strane málokto z nich sa vyzná v kartografii. Takže väčšina občanov si vyzdvihne na úrade prázdnu žiadosť, vyplní do nej nejaké náhodné čísla a zájde s ňou späť na úrad. Pokiaľ dostane žiadosť, ide loviť ryby, pokiaľ nie, vyzdvihne si ďalšiu. A štát veselo zarába. Tak si to aspoň všetci vo vláde predstavujú.
Jediné, čo chýba, je program, ktorý by veľmi rýchlo vedel rozhodovať o žiadostiach, či ju treba prijať alebo zamietnuť. Na úradoch sa totiž čakajú také návaly, že nebude v silách úradníkov zvládnuť ich bez pomoci výpočtovej techniky.
Úloha
Priživte sa spolu s kiribatskou vládou na udeľovaní povolení na rybolov a napíšte program, ktorý bude prijímať a zamietať žiadosti podľa vyššie uvedeného popisu. Program dostane vo vstupnom súbore mapu Kiribati v nasledovnom formáte: Prvý riadok obsahuje dve čísla M, N - počet riadkov a stĺpcov mapy. Ďalšie riadky obsahujú samotnú mapu, pričom j-ty znak v i-tom riadku je 1, ak je vo štvorci [i,j] pevnina, resp. 0, ak je tam more.
Po spustení má váš program načítať mapu, prípadne si niečo dopredu pripraviť a potom čítať zo vstupu dôležité údaje žiadostí. Každý riadok bude obsahovať 4 čísla - súradnice dvoch protiľahlých rohov oblasti, o ktorú občan žiada. Program má vypísať pridelit alebo zamietnut podľa toho, či je v tejto oblasti len more alebo aj pevnina. Je dôležité, aby váš program vedel o ľubovoľnej žiadosti rozhodnúť čo najrýchlejšie.
Príklad
Vstup
Mapa
8 10
0000000000 0000000010 0011000110 0111100000 0000110000 0000001000 0111000000 0000000000
Žiadosti 1 1 2 3
3 3 3 3
8 10 1 1
1 7 4 6
Výstup
prideliť
zamietnuť
zamietnuť
prideliť
5. Zablúdená správa
ERPAATNIC__PNOAJEEASJTSIOE_DVRENERM_EPDMR_TEK,TOSOY_ZME_ AILUTZ_NVR_UZDIAAEAN_ISTJIBITLY__NEDCIOVOHDRUU_HESMOA_PI R_NSK,TO__YCVHEKPOVYKSO_JRREAKCUNEE_DMIAVJ_TTEO__CELIINY ISNAT_AT_CSTKIOMVOSURBE__KSEYTCHHUZICJICOD_JIENC_OV_HTTO SHDRUU,_L_A_RUEF_AEKNTTAEKATUA_SA_LMCYELDCDEA_NITSAET_RE E_A_USSP_MCH_OZALCAKHYKOM_VEPKOD_OIEKN._
"Táto správa musela určite zablúdiť," povedalo si Ministerstvo Špionáže po tom, ako sa ich najlepším odborníkom na poli kryptografie túto správu nepodarilo rozlúštiť. A ešte k nej bol pribalený aj obrázok... "No to si najskôr nejaké dieťa krátilo svoj voľný čas a nám vyrábalo starosti!"
Ale možno... čo ak predsa táto správa niečo hovorí? Keby sme aspoň vedeli, akým spôsobom bola táto šifra vyrobená... Znak '_' označuje medzeru, nikde inde v texte medzery nie sú. Pokúste sa Ministerstvu pomôcť rozlúštením tejto správy a opísaním šifrovacej metódy.
(c) 23. Januára 2002 webmaster
