- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Príklady 2. kola letnej časti 22. ročníka KSP-Z
Milí riešitelia!
Tu tú, di du du
Tu tú du du
Tu tú di du du di du du di du du dutú tu du tu
Mahna Mahna
M-ahna M-ahna ma 2. mája 2005 M-ahna mana mana ma M-ahna M-ahn...
KSPáci
1. Zvrátená učiteľka
(15 bodov)
ozor, tento príbeh je veľmi smutný a obsahuje zmienky o násilí páchanom na deťoch. Preto odporúčam, aby ste pri čítaní sedeli. Bola raz jedna učiteľka v škôlke, ktorá mala veľmi rada matematiku. Keďže 5-ročné deti ešte nevedia počítať, tak sa rozhodla, že ich to naučí, aby sa mala s kým rozprávať. Najprv ich musela naučiť čísla a za tým účelom vymyslela nasledujúcu nudnú hru. Učiteľka postavila n stoličiek do radu, a na každú si sadlo jedno vystrašené dieťa. Potom ešte na stoličky napísala náhodne čísla od 1 po n (na každú jedno a žiadne dve stoličky nemali rovnaké čísla).
Deťom rozkázala, že keď tleskne, majú sa postaviť a sadnúť si na toľkú stoličku zľava, aké je číslo na tej stoličke, kde sedeli. Deťom sa takáto hra vôbec nepáčila a na začiatku im to ani nešlo, ale zato učiteľka sa veľmi dobre zabávala. Tlieskala, plieskala a zákerne sa pri tom usmievala... . Ako sa tak hrali, učiteľke sa zrodil v hlave skvelý nápad: "A teraz retrospektívne! Ako keď sa pretáča video dozadu, to bude sranda, keď tlesknem, tak sa vrátite o krok späť", ale deti na to sklamane: "Ale my si nepamätáme, kde sme kedy sedeli, veď to už hráme 3 dni v kuse, mohli by ste nás už aj domov pustiť, aj pospať by sme si mohli...". "Ja vám dám, vy lamy, že pospať...", skríkla učiteľka a dodala: "Veď pamätať si nemusíte nič, keby ste vedeli algebru, tak viete, že to, kam si máte sadnúť, keď tlesknem, sa dá zistiť z očíslovania stoličiek. Lamy, he-he". Ale deti sú už totálne zmagorené, takže im budete musieť pomôcť vy, lebo ináč ich začne učiť aj algebru, a to si ani ja nechcem predstaviť, aké hrozné hry im potom vymyslí...
Úloha
Na vstupe je číslo n, a postupnosť celých čísel A1, A2,..., An, kde Ai je číslo na i-tej stoličke. Napíšte program, ktorý vypíše postupnosť čísel B1,B2,...,Bn, kde Bi bude číslo stoličky, kam si ma sadnúť dieťa sediace na i-tej stoličke po tom, ako učiteľka zatlieska (v rámci toho, že majú ísť retrospektívne).
Bonusová otázka: vymyslite pre takúto hru nejaký pekný názov, najlepšie odpovede budu ohodnotené.
Príklad
Vstup
N=5
2 3 4 5 1
N=5
3 1 4 2 5
Výstup
5 1 2 3 4
2 4 1 3 5
2. Z kalendára
(15 bodov)
Najobľúbenejšie dievča v 1.A je Karolína. Aj vy by ste si ju obľúbili. Nikdy by totiž nezabudla na vaše narodeniny (a keď si niekto spomenie na vaše narodeniny, je reálna šanca, že vám donesie aspoň čokoládu). Pamätala by si aj koľko máte rokov a kto sa narodil v rovnaký deň, mesiac alebo rok ako vy. Karolínkine spolužiačky jej nesmierne závidia a šuškajú si, že v tom bude nejaký fígeľ. Ako to môže všetko vedieť a pritom si ani nepamätá, kedy bola bitka pri Kreščaku (no schválne, kedy ;-))?! A fígeľ v tom naozaj je. Karolína má doma databázu dátumov narodení všetkých svojich spolužiakov, kamarátov, a vôbec. Každé ráno, skôr než odíde do školy, zadá počítaču dátum a počítač jej vypľuje, kto sa vtedy narodil. Takto zistí všetko, čo potrebuje. (V tom, že má ráno čas na takéto hlúposti, bude tiež nejaký fígeľ, ale to je o inom.) Ak sa chcú spolužiačky Karolíne vyrovnať, potrebujú si napísať program, ktorý bude robiť to isté.
Úloha
Na vstupe budú zadané dátumy narodenia ľudí v tvare: deň mesiac rok. Vašou úlohou je napísať program, ktorý ako odpoveď na popis časového úseku vypíše všetkých, ktorí sa vtedy narodili. Popis časového úseku je opäť v tvare deň mesiac rok, pričom ľubovoľný z parametrov môže byť nahradený hviezdičkou (s významom "všetky"). Teda ak chceme všetkých ľudí narodených v januári, hocijaký deň a rok, napíšeme: * 1 *, ak to má byť presne 17. január 1987, napíšeme 17 1 1987.
Príklad
Vstup
Databáza:
jano 2 3 1985
marek 24 12 1990
matus 29 7 1985
lukas 12 3 1986
Požiadavka:
* * 1985
Výstup
jano matus
3. Zachránená škôlka
(15 bodov)
Malý Quido svojimi chlapčenskými vrtochmi (Jeden z jeho vrtochov je, že sa rád háda, či prvé písmeno jeho mena patrí do slovenskej abecedy. Ale to už je iný príbeh...) spôsobil, že sa v jeho škôlke už žiadne dve dievčatá nekamarátia. Rád by teraz dal všetko do poriadku, aby sa znovu kamarátila celá škôlka, a teda aj každé dve dievčatá (chlapci rozhádaní nie sú). Vie, že keď obetuje niekoľko cukríkov, budú sa niektoré dve dievčatá znovu kamarátiť. A keďže platí, ako to už v škôlke medzi dievčatami býva, že ak si moja kamarátka, tak aj všetky tvoje kamarátky sú mojimi kamarátkami, nebude to mať Quido až také ťažké. Tak si aspoň povedal, že na uzmierovanie minie čo najmenej cukríkov - aby mu ich čo najviac zostalo.
Úloha
Na vstupe budete mať dve čísla - počet dievčat n a počet dvojíc dievčat m, ktoré by Quido ešte mohol cukríkmi udobriť. Nasledovať bude m trojíc ai, bi, ci (1 <= ai,bi <= n), ktoré budú znamenať, že dievčatá ai a bi sa budú znovu kamarátiť, keď sa s nimi dvomi Quido chvíľu zahrá a zjedia pritom spolu ci cukríkov. Žiadne dve dievčatá sa na začiatku nekamarátia. Vašou úlohou je vypísať niekoľko dvojíc xi a yi, aby platilo, že potom ako Quido udobrí tieto dvojice, už sa budú kamarátiť všetky dievčatá (bude teda platiť, že každé dve dievčatá budú spriatelené priamo alebo cez niekoľko ďalších kamarátok). Navyše musí platiť, že tento spôsob bude stáť Quida najmenší možný počet cukríkov. Môžete predpokladať, že existuje aspoň jeden spôsob, ako spriateliť všetky dievčatá.
Príklad
Vstup
n=7, m=9
1 2 47
2 3 6
3 5 1
2 4 3
4 5 2
5 6 2
3 6 1
4 7 1
6 7 3
Výstup
1 2
2 4
3 5
4 5
3 6
4 7
(Takéto skamarátenie bude stáť len 55 cukríkov.)
4. Zobudené veveričky
(15 bodov)
Ako všetci isto viete z hodín biológie alebo prírodopisu, veveričky sa neukladajú na zimný spánok. Tento rok sa zima nejako natiahla a veveričky zistili, že nemajú čo jesť. Našťastie všetky bývajú na strome, kde rastú veľké a chutné orechy. Síce sú ešte z minulého roka, ale veveričky vedia, že hlad je najlepší kuchár.
Každá veverička býva buď v mieste, kde sa konáre stromu stretávajú, alebo kde sa nejaký konár končí. Navyše v každom takomto mieste býva práve jedna veverička a medzi každými dvoma domčekmi existuje práve jedna cesta. Po dlhej zime zostalo na strome presne toľko orechov, koľko tam býva veveričiek. A keďže veveričky vedia, kde majú stavať domčeky, orechy rastú hneď vedľa ich domčekov (priam zanedbateľne ďaleko). Lenže niektoré veveričky majú pri dome veľa orechov a niektoré ani jeden.
Rozhodli sa, že sa spravodlivo rozdelia, teda každá dostane jeden orech, ale naviac by chceli, aby sa dokopy nachodili čo najmenej. Každá veverička musí ísť totiž po orech, ktorý jej bol určený, a potom ísť naspäť do svojho domčeka.
Úloha
Najprv je na vstupe zadané číslo N, ktoré označuje počet orechov, veveričiek a aj domčekov. Ďalej nasleduje N čísel, ktoré označujú počet orechov pri domčekoch 1 až N. Potom je na vstupe zadaných N-1 dvojíc (xi, yi), ktoré určujú obidva koncové domčeky i-teho konára. Vašou úlohou je nájsť najkratšiu vzdialenosť, akú musia dokopy prejsť veveričky.
Príklad
Vstup
N=9
2 1 0 1 3 0 0 2 0
1 2
1 3
3 5
3 6
1 4
4 9
4 8
4 7
Výstup
14
(Veveričky z 3. a 6. domčeka pôjdu k 5. domčeku, 9. veverička pôjde k 8., 7. veverička k 1. domčeku)
5. Zamyslite sa
(15 bodov)
Ako obvykle, aj túto sériu je posledný príklad netradičný. Zamýšľali ste sa niekedy nad tým, čo stojí za príkladmi, ktoré my vytvoríme a vy riešite? Máte teraz príležitosť vyskúšať si časť povinností vedúceho KSP.
Vašou úlohou je vymyslieť príklad, ktorý by svojou obtiažnosťou zodpovedal KSP-Z. Teda nemal by byť príliš ľahký, ale zase by ste mali byť schopní ho vyriešiť (a nie len vy, ale aj ostatní riešitelia KSP-Z). Okrem vymyslenia príkladu požadujeme aj priloženie vzorového riešenia (aj programu), spolu s ohodnotením jednotlivých druhov riešení. Napríklad vzorové riešenie má časovú zložitosť O(N.logN) a pamäťovú O(N). Za funkčné riešenie by ste udelili 15 bodov. Za riešenie s pamäťou O(N2) 12 bodov atď. Samozrejme by sa mala dať daná úloha s takou zložitosťou aj vyriešiť (čiže nejedná sa len o hypotetické riešenia). Inak povedané, požadujeme "návod" ako daný príklad opravovať.
Úloha
Okrem toho, príklad, ktorý pošlete, by mal byť dostatočne neznámy. Ak napríklad pošlete príklad, ktorý bol v KSP-Z pred rokom, tak očakávajte minimum bodov - až 0. Rovnako príklad, ktorý sa dá ľahko "vygúgliť" dostane málo bodov. Naopak kreatívne riešenia (resp. zadania) dostanú bodov veľa.
Príklad
Ostatné príklady v tejto sérii, keby boli neznáme ;-)
© KSP, 12. apríla 2005
