- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Príklady 2. kola letnej časti 21. ročníka KSP-Z
Milí riešitelia!
Tak nám po dlhej zime vykuklo slniečko a jar zaklopala na dvere. Príroda rozkvitá, zvieratá sa zobúdzajú zo zimného spánku a medzi iným sme sa prebudili aj my a dali sa do práce. A tak sa Vám konečne dostáva do rúk čerstvé a ešte teplé KSPčko. Riešenia tohto kola nám posielajte do 31. mája 2004 a nezabudnite priložiť pár známok v hodnote okolo 15 korún, aby sa Vám mohli aj bez problémov opravené vrátiť.
KSPáci
1. Zo života informačnej kancelárie II
(15 bodov)
V meste Kocúrkovo už dlho funguje informačná kancelária. A kedže ešte stále pri príchode ľudí ponúkajú pohárom chladeného piva, ľudí je tu stále dosť a stále sú tu rady. Avšak ľudí nebaví stáť v radách a radi sa predbiehajú. To sa samozrejme tým predbiehaným nepáči (komu by sa už páčilo) a tak dosť často vnikajú spory. Nový starosta sa rozhodol, zabrániť sporom a zmodernizovať túto kanceláriu. Dal namontovať mašinku, ktorá rozdáva lístočky s poradovými číslami, v ktorých ľudia prichádzajú do informačnej kancelárie. Táto mašínka začala s číslom 1 a pokračuje s ostatnými prirodzenými číslami (nikdy sa nedostane späť k číslu 1). To ale nebolo všetko! Kedže je to Kocúrkovo, starosta zmenil aj číslovanie okienok a okienka označil všetkými prvočíslami. Okienka si postupne volajú poradové čísla ľudí, ktoré svietia na veľkej svetelnej tabuli. Ak je okienko prázdne alebo sa uvoľní, na svetelnej tabuli sa zobrazí najmenšie poradové číslo čakajúceho občana, ktoré je deliteľné číslom okienka a tento občan sa môže k nemu dostaviť. Vašou úlohou je pomôcť starostovi zrealizovať tento plán.
Úloha
Napíšte program, ktorý bude riadiť privolávanie čakajúcich pomocou svetelnej tabule. Na začiatku načíta číslo K, udávajúce, že funguje prvých K okienok. Okná sú očíslované prvými K prvočíslami. Váš program bude na vstupe dostávať správy tvaru PRISIEL a UVOLNILO SA X. Výstupom po správe PRISIEL bude poradové číslo občana, ktorý práve prišiel. Správou UVOLNILO SA X sa uvoľní okienko číslo X (kde X je nejaké prvočíslo). Váš program má vždy, keď sa uvoľní okienko a niekto čaká, zavolať k nemu čakajúceho občana, ktorého poradové číslo je najmenšie spomedzi čísel čakajúcich občanov, ktoré je deliteľné číslom X. Ak sú v okamihu, keď príde občan, voľné niektoré z okienok, ktoré ho môžu obslúžiť, je rovno zavolaný k tomu z nich, ktoré má najmenšie číslo. Kedže kancelária funguje non-stop, váš program by mal tiež bežať bez prerušenia.
Príklad
K=5
Vstup: PRISIEL Výstup: Prišiel občan číslo 1. Vstup: PRISIEL Výstup: Prišiel občan číslo 2. Výstup: Občan s poradovým číslom 2 prosím k okienku 2. Vstup: PRISIEL Výstup: Prišiel občan číslo 3. Výstup: Občan s poradovým číslom 3 prosím k okienku 3. Vstup: PRISIEL Výstup: Prišiel občan číslo 4. Výstup: UVOLNILO SA 3 Vstup: PRISIEL Výstup: Prišiel občan číslo 5. Výstup: Občan s poradovým číslom 5 prosím k okienku 5. Vstup: PRISIEL Výstup: Prišiel občan číslo 6. Výstup: Občan s poradovým číslom 6 prosím k okienku 3. Výstup: UVOLNILO SA 2 Výstup: Občan s poradovým číslom 4 prosím k okienku 2.
2. Zaba neblázni
(15 bodov)
Krotiteľka Zaba má vo svojej nemalej zbierke veľmi veľa zvieratiek. A nechýbajú jej tam ani žabky. Nacvičila s nimi jednoduché číslo: Žabky sedia na malých lavičkách očíslovaných od 1 do N. Vždy, keď Zaba tleskne, všetky žabky vyskočia a opäť na každú lavičku dopadne práve jedna z nich. Tlesk – a znova sedia ináč. Tlesk – a zase.
Tajomstvo, prečo sa nikdy žiadne žabky nezrazia, je jednoduché – pre každú lavičku je jednoznačne povedané, kam má žabka, ktorá na nej sedí, skočiť.
Úloha
Je dané číslo N = počet žabiek = počet lavičiek. Nasleduje N čísel, i-te z nich je číslo lavičky, na ktorú skáče žabka sediaca na i-tej lavičke. Tieto čísla sú navzájom rôzne. Napíšte program, ktorý zistí, či ešte niekedy budú žabky sedieť tak, ako sedeli na začiatku. Ak áno, zistite, koľkokrát musí Zaba tlesknúť, aby sa tak stalo.
Príklad
Vstup
N=7
2 4 3 1 7 5 6
Výstup
Zaba musí tlesknúť 3-krát.
(na začiatku: a b c d e f g
1.tlesk: d a c b f g e
2.tlesk: b d c a g e f
3.tlesk: a b c d e f g)
3. Zo sveta motovodu
(15 bodov)
Motovod je ekologický dopravný prostriedok. Nechodí na benzín, ani na uhlie, ale energiu načerpá vždy, keď prejde po moste. Preto ho Dopravný podnik využije, iba ak môže pri každej svojej ceste prejsť po moste. Motovod teda zjavne nemôže využívať ľubovoľné mesto. Môže ho využívať len také, ktoré má rieku a každá cesta medzi dvoma zastávkami vedie krížom cez rieku. Dopravný podnik poslal mapu dopravnej siete, ale nie je tam zakreslená rieka. Dodávateľ motovodov si už-už chcel kúpiť mapu s riekou, keď tu dostal nápad. Čo ak už z tejto mapy je jasné, že niektoré dve susedné zastávky musia ležať na tom istom brehu? V takom prípade môže na toto mesto rovno zabudnúť.
Úloha
Je dané číslo N = počet rôznych zastávok a M = počet ciest. Nasleduje M dvojíc čísel, ktoré predstavujú cesty. Vašou úlohou je napísať program, ktorý zistí, či má zmysel kupovať mapu s riekou.
Príklad
Vstup #1
N=7 M=8
1-4, 1-7, 2-3, 2-4,
3-5, 3-6, 4-5, 6-7
Výstup #1
Áno
(Možno sú na ľavom brehu práve zastávky 1, 2, 5, 6)
Vstup #2
N=3 M=3
1-2, 2-3, 3-1
Výstup #2
Nie
(Niektoré dve susedné zastávky určite ležia na tom istom brehu)
4. Zeofína v záhrade II
(10 bodov)
Naša korytnačka má už peknú trávovú záhradu obdĺžnikového tvaru, a tak sa ju rozhodla kreatívne využiť. Namočila si chvostík do farby, a na kúsku záhrady nakreslila štvorcovú sieť. Potom sa po nej poprechádzala, a zmazala farbu zo všetkých štvorčekov, ktoré ležali v každom treťom stĺpci a v každom treťom riadku. (Počítať začína od ľavého dolného rohu.) Ostal jej taký útvar ako na obrázku.
Toto sa jej tak páčilo, že sa rozhodla nakresliť si takúto sieť väčšiu. Ale keďže už z malej má pomotanú hlavu, obrátila sa na vás.
Úloha
Napíšte program, ktorý na vstupe dostane čísla n, m a vypíše korytnačke návod, ako má kresliť, aby obrazec rozmerov n× m nakreslila. Aby šetrila farbou, bola by Zeofína rada, keby kreslila každú časť iba raz. Chodiť po už nakreslenom však môže. Zeofína rozumie nasledujúcim príkazom:
- dopredu k – pohla sa k korytnačích metrov dopredu (k je reálne),
- doprava u – otočila sa o u stupňov doprava,
- doľava u} – otočila sa o u stupňov doľava
- hore – zdvihne chost, namočený vo farbe, aby nezanechávala stopu
- dole – položí chvost, aby zanechávala stopu
Príklad
Vstup
2 4
Výstup
DOLE; DOPREDU 4; DOPRAVA 90; DOPREDU 1; HORE; DOPREDU 1; DOPRAVA 90; DOPREDU 2; DOLE; DOPRAVA 90; DOPREDU 2; HORE; DOPRAVA 90; DOPREDU 1; DOPRAVA 90; DOLE; DOPREDU 1; DOPRAVA 90; DOPREDU 2; DOPRAVA 90; DOPREDU 1; HORE; DOLAVA 90; DOPREDU 1; DOLE; DOLAVA 90; DOPREDU 1;
5. Z denníčka
(15 bodov)
19.4.2004: Mám napísať zadanie do KSP-čka. Prečo ja??? Povedali, že sa priveľa hrávam. Nezmysel. A navyše ešte tá hlúpa stávka. Vraj sa nemám týždeň hrať. Dostanem za to kofolu. Ľahké. Len mám teraz nejako veľa času, zadanie sa napíše potom, zatiaľ si asi pozriem nejaký pekný film. Ostatní mi tvrdia, že je to lepšie ako hry a vraj najlepšie je čítať nejakú knižku. Nuž, možno. Veď vyskúšam. No nič nateraz končím.
20.4.2004: No, hry sú predsa len trochu lepšie ako filmy. Aspoň včerajší, bol dóóóósť nudný. Pustila som to štyrikrát a naozaj si myslím, že prejsť posledným levelom bez nárazu sa nedá. A navyše, ovládač má dosť nešikovné tlačítka. Sú malé, blízko seba, nedá sa to poriadne držať v dvoch rukách. Knihy sa tiež ukázali ako dobrý vtip. Tomuto hovoria grafika? Jeden obrázok (a ešte k tomu statický, predstav si to, milý denníček) na 100 stranách. Zvyšok hustý text. Ešte aj boje boli obkecané. Dostala som sa na 47-mu stranu a stále som nevedela koľko mám životov, ba ani za ktorú postavu hrám. Skrátka podvod. A ani sa neobťažovali pekným introm. Ohó a spomenula som? Nemalo to žiadne zvuky. Vlastne ani nebolo kde pripojiť repráky. Idem spať. Dnes to naozaj nemá cenu.
21.4.2004: A ja viem? To sú nápady. Že vraj zadanie. Vraj ho mám napísať. Ale mne sa nechce, ja sa chcem hrať. Ach, hry moje milované, akože mi chýbate. Dnes je deadline na zadanie. Ten lahodný zvuk motorov, slastná ozvena výstrelov. Inak, niekedy som fakt dobrá, to mi ver milý denníček. Takto dnes poobede som si nenápadne, keď všetci odišli pustila <cenzurované – reklama>. A dostala som ich všetkých. Dôležité je dôsledne sa kryť a pamätať si, kde sú všetky lekárničky.
Rozprávka? Ále netreba. hlavne že bude popis. Hmmm ale aký? Hm hm hmmmmm. Ahá už to mám! Našla som peknú hru volá sa Sokoban. Je to starinka, ale čo už. A má to málo levelov. Tak nech mi pošlú nejaké nové. Malé, ale ťažké. A je to.
22.4.2004: Zadanie som odovzdala neskoro, boli na mna jemne nas... nahnevaní. A k tomu som prišla o kofolu. Prichytili ma. Ale mám High Score! Huraaaaaaa. Ide sa oslavovaaaať!
Úloha
Úlohou je zostrojiť čo najťažší level Sokobanu. Vyzerá to asi takto: v štvorčekovej sieti je symbolom # ohraničená miestnosť. # označuje stenu a môže sa nachádzať aj niekde vnútri miestnosti. Niekde dnu sú bedničky označené symbolom $ a panáčik @. Panáčik sa vie pohybovať hore, dolu, doprava a doľava. Ak pred panáčikom stojí bednička a pred ňou je prázdne miesto panáčik vie bedničku pusunúť. Cieľom je presunúť bedničky na miesta označené bodkami (.). (Bedničku stojacu na nejakej bodke označíme *)
Level je tým ťažší, čím je najkratšie riešenie dlhšie. T.j. pošlite nám level, ktorého najkratšie riešenie je čo najdlhšie. Ak si nie ste istí, ktorý z vašich levelov je lepší, môžete nám ich poslať až 5, hodnotí sa najlepší.
Aby to nebolo také ťažké, v miestnosti môžu byť najviac tri bedničky, voľná podlaha môže mať rozmery najviac 6×6. Panák nemôže začínať na mieste, kde má skončiť kocka.
Príklady posunu panáka: Na jeden posun (rozumej ľahký príklad)
##### #####
z #.$@# na #*@ #
##### #####
Na 10 posunov (rozumej ťažší príklad)
######## ######## ######## ######## ######## ########
#. *# #. *# #. *# #. *# #. *# #. *#
z # $ # na # $ # , # $ # , # $ # , # $@ # , # $@ #
# @# # @ # # @ # # @ # # # # #
######## ######## ######## ######## ######## ########
######## ######## ######## ########
#. *# #. *# #. *# #* *#
a ďalej #$@ # , #$ # , #$ # , #@ #
# # # @ # #@ # # #
######## ######## ######## ########
Jeden ukážkový level (zďaleka nie najlepší!)
######## #. . .# # ## # # ## # ## #$ $$ # # # @# ########
© KSP, 25. apríl 2004
