- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Príklady 1.kola zimnej časti 20.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 XX. ročníka KSP-Z. Prečítajte si pozorne pravidlá súťaže a (ak na túto kategóriu ešte nie ste "služobne pristarí") hor sa riešiť. Svoje riešenia nám posielajte najneskôr do 21. októbra 2002. Nezabudnite k nim priložiť známky v hodnote 15,- Sk.
KSPáci
1. Zatopenie Brezna
(15 bodov)
Počas tohoročných záplav si vraj "čierneho Petra" vytiahlo Brezno. Napriek tomu nestihol Hron vytopiť ani len garáž, v ktorej odpočíval Braňov bicykel. Chýbalo vraj málo. Ale koľko vody môže ešte tiecť v Hrone, aby garáž nezaplavilo?
Úloha
Na vstupe je N - vzdialenosť garáže od Hrona a čísla a1, ..., an - profil krajiny medzi garážou a Hronom. Presnejšie vo vzdialenosti i metrov od Hrona je výška terénu ai mnH (metrov nad Hronom). Hron tečie úplne vľavo (na nultom metri, vo výške 0 mnH). Voda v Hrone tečie konštantnou rýchlosťou 1 m/s bez ohľadu na počasie. Keď voda stúpa, tak sa rovnomerne rozlieva, až pokiaľ to terén dovolí. Zistite, o koľko metrov kubických za sekundu môže ešte stúpnuť prietok vody v Hrone, aby nezaplavilo garáž.
Príklad
Vstup #1
N=5
1, 3, 1, 0, 2
obrázok pre prvý prípad
Výstup #1
8
Vstup #2
N=4
1, 0, -1, -2
Výstup #2
1
2. Z gaštanov
(13 bodov)
Začala sa jeseň. Na jeseň sa začína škola. No a náš Mišo sa začal znova nudiť v škole. Takže, čo taký Mišo nevymyslel... keď je tu tá jeseň, tak by si mohol stavať z gaštanov panáčikov. Tak to aj spravil. Zobral hŕbu gaštanov, zápaliek a začal. Spájal, spájal a už nevie ani ako, ale podarilo sa mu urobiť hŕbu figúrok. Ale teraz má problém: nevie zistiť, koľko vlasne je týchto jeho výtvorov.
Úloha
Napíšte program, ktorý načíta N - počet gaštanov (gaštany sú očíslované od 1 po N), M - počet spojení zápalkami a zoznam dvojíc čísel gaštanov, ktoré sú navzájom spojené (zápalkou). Váš program má vypísať počet útvarov, ktoré Mišo vytvoril.
Príklad
Vstup
N=9, M=7
1 2 2 3 2 4 2 7 5 7 6 7 8 9
Výstup
Mišo vytvoril 2 útvary.
(Vytvoril koníka a činku. :)
3. Zvianočnieva sa
(13 bodov)
Ako iste viete, prišla už jeseň a s ňou nastala pre mnohých z vás obrovská kopa problémov, ako napríklad škola. Ale asi len Paľko si všimol, že vianoce sú už predo dvermi a začal si už zháňať vianočný stromček, aby si ho nemusel kupovať 25. decembra ako po minulé roky. Preto sa vybral do lesa a našiel si tú svoju najkrajšiu a najkošatejšiu jedličku, aká tam rástla a s pomocou susedovho traktora si ju priviezol domov.
Pri pokuse o prestrčenie jedličky cez dvere do obývačky však zistil, že jedlička je na to príliš široká a vysoká. Preto sa rozhodol odpíliť kúsok zdola tak, aby mu ostal stromček, ktorý už prejde dverami a je čo navyšší. Ale ako to urobiť? Preto sa obrátil na vás s prosbou, aby ste mu s tým pomohli.
Predpokladajme pre jednoduchosť, že stromček je dvojrozmerný a nemôžeme ho otáčať. Predstavte si ho ako zvislý kmeň (úsečku), z ktorého vyrastajú vodorovné konáre. Z jedného miesta na kmeni vždy vyrastá dvojica konárov rovnakej dĺžky - do každej strany jeden. Aby ten stromček nejako vyzeral, dĺžka nižšie položeného konára je vždy väčšia alebo rovná ako dĺžka vyššie položeného konára. Hrúbku konárov a kmeňa je možné zanedbať.
Úloha
Napíšte procedúru, ktorá dostane ako parametre 3 čísla K, L, M - šírku dverí, výšku dverí a výšku stromčeka. Ďalej číslo N - počet rozkonárení stromčeka a N-prvkové pole s popisom jednotlivých rozkonárení. Rozkonárenie popíšeme jeho vzdialenosťou od vrchu stromčeka a dĺžkou konárov, ktoré z neho vychádzajú. Môžete predpokladať, že toto pole je na začiatku usporiadané vzostupne podľa vzdialenosti od vrchu stromčeka. Vaša procedúra má zistiť, či treba stromček rozpíliť a ak áno, tak aj miesto jeho rozpílenia.
Poznámky
Formát parametrov si môžete podľa ľubovôle upraviť alebo z nich spraviť globálne premenné. Snažte sa nájsť riešenie, ktoré sa bude potrebovať pozrieť na čo najmenej rozvetvení stromčeka.
Príklad
Vstup
K=100, L=140
M=120, N=5
A=((10, 5), (30, 15), (50, 35), (60, 55), (100, 70))
Výstup
Stromček treba rozpíliť tesne nad 4. vetvou.
4. Žiarovky
(15 bodov)
Ako ste sa v prvom príklade tejto série dozvedeli, hrozí, že Brezno zatopí voda. Požiarnici museli všetkých obyvateľov Brezna rýchlo evakuovať, aby sa neutopili. Preto ich ukryli do podzemného krytu. (Z blata do kaluže. To viete, Brezno...) Taký kryt sa skladá z množstva na seba kolmých chodieb, ktoré sa navzájom križujú. Na každej križovatke je jedna žiarovka a na konci každej chodby je prepínač, ktorý prepína všetky žiarovky na križovatkách tejto chodby (zapaľuje všetky zhasnuté žiarovky a zhasína všetky zapálené žiarovky). Keďže požiarnici nechcú, aby sa obyvatelia v panike pošliapali, chcú rozsvietiť všetky žiarovky. Vašou úlohou je zistiť, či sa to dá, a ak áno, tak na koľko najmenej prepnutí.
Úloha
Kryt sa dá predstaviť ako matica žiaroviek N x M, kde riadky a stĺpce matice sú chodby. Je dané číslo N - počet riadkov matice, číslo M - počet stĺpcov matice a matica N x M popisujúca aktuálny stav žiaroviek - 0 znamená, že žiarovka je zhasnutá a 1 znamená, že žiarovka je zapálená. Vašou úlohou je vypísať najkratšiu postupnosť riadkov a stĺpcov matice, v ktorých keď prepneme žiarovky, tak budú všetky svietiť. Ak je takých postupností viac, vypíšte ľubovoľnú z nich. Ak neexistuje žiadna taká postupnosť, vypíšte správu: "Rozsvietiť všetky žiarovky sa nedá."'.
Príklad
Vstup #1
N=4
M=6
1 0 1 1 1 0 1 0 1 1 1 0 0 1 0 0 0 1 1 0 1 1 1 0
Výstup #1
2. stĺpec
3. riadok
6. stĺpec
Vstup #2
N=3
M=5
1 0 1 1 1 0 1 0 1 1 1 0 1 1 1
Výstup #2
Rozsvietiť všetky žiarovky sa nedá.
5. Zahltení prácou
(18 bodov)
Veru tak. V Softvérovom Družstve SoDr majú opäť frmol. Práce vyše hlavy a ešte toto. Totiž včera za nimi prišiel zástupca spoločnosti HP (Pozor! Nie Hewlett-Packard}, ale Harry Potter) a požiadal ich o pomoc. Firma HP sa chystá vypustiť do sveta novú verziu hry "Harry Potter a smradľavé slimáky", v ktorej sa bude Harry nachádzať v akomsi bludisku v podobe záhrady, zámku, a pod., a bude sa vyhýbať smradľavým slimákom a jesť fazuľky. Programátori firmy HP už zvládli všetko okrem časti programu, ktorá by do jednotlivých levelov mala generovať bludiská.
Niežeby sa členom SoDr nechcelo nič programovať, to sa nedá povedať. Akurát, momentálne riešia (dôležitejšie) problémy sveta a logicky sa takýmto niečím nemajú čas zaoberať. Preto pre zmenu oni požiadali o pomoc vás.
Úloha
Vašou úlohou je napísať program, ktorý pre zadané rozmery bludiska M x N vygeneruje mapu bludiska. Mapa sa skladá zo znakov "X", ".", "s", "c", pričom "X" predstavuje stenu, "." chodbu, "s" miesto, kde sa Harry ocitne na začiatku a "c" miesto, kam sa má Harry dostať. V bludisku by mala navyše existovať aspoň jedna cesta z miesta označeného znakom "s" do miesta označeného znakom "c" prechádzajúca iba chodbami. Do zadaných rozmerov sa nepočíta "stena" okolo celého bludiska. Ďalej môžete predpokladať, že M >= 5 a N >= 5. Snažte sa, aby váš program vygeneroval zakaždým čo najzaujímavejšie (najnamakanejšie :-) bludisko! Okrem toho, pošlite nám bludiská (vytlačené na papieri), ktoré váš program vygeneroval pre rozmery 10 x 10, 7 x 20 a 22 x 78.
Príklad
Vstup
M = 10, N = 10
Výstup
XXXXXXXXXXXX X...X.X....X X.X.X...XX.X X.X.XXX.X..X X.X...X....X X.X.X.X.X..X X.X.X.X.X..X X.X.X.X.XX.X X.X......X.X X.XXXXXXXX.X X...sXc....X XXXXXXXXXXXX(Toto je len jedno možné bludisko.)
(c) 24. septembra 2002 webmaster
