- 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-Z
Milé naše riešiteľky, mílí naši riešitelia,
srdečne vás pozývame riešiť nový ročník KSP-Z.
Sme radi, že si čítate tieto riadky, lebo to pravdepodobne
znamená, že sa stanete našimi riešiteľmi. Ako odmenu pre
najlepších riešiteľov pripravujeme jarné sústredenie.
Aby ste sa tam dostali, doporučujeme vám prečítať si pravidlá.
Riešenia posielajte najneskôr do 8. novembra 2004 a
nezabudnite do obálky priložit známky v hodnote 15,-Sk.
Ak neviete, ako by malo vaše riešenie vyzerať, môžete
navštíviť našu stránku: http://www.ksp.sk/ksp,
nájdete sa tam kopu vecí, ktoré sa do tohto letáku nevôjdu.
KSPáci
1. Zruční artisti
(15 bodov)
Artisti v cirkuse Kaledon začali nacvičovať novú zostavu. Ich zostava je však veľmi obtiažna -- či už na koordináciu pohybov, alebo fyzickú silu artistov. Hlavne druhá zložka cviku je pre nich náročná, keďže koordináciu už zvládli v predošlých cvikoch. Chcú postaviť vežu tak, že sa postupne naskladajú na seba. Ich problém spočíva v tom, že im zostava nevychádza, lebo nie sú schopní udržať jeden druhého. Pomôžte im tento problém vyriešiť. Ešte vám vedia povedať, že každý artista vie udržať kolegu na sebe pokiaľ váži nanajvýš toľko, čo on sám.
Úloha
Na vstupe je zadané prirodzené číslo N. Ďalej nasleduje N čísel, ktoré vyjadrujú hmotnosť každého artistu. To je zároveň aj najväčšia hmotnosť artistu, ktorý mu môže stáť na pleciach. (Stačí ak artista unesie toho priamo nad sebou, na váhe ostatných artistov nad ním nezáleží. To preto, že najtažšia časť je zachytiť kamaráta v okamihu, keď ti dvojitým saltom vyskočí na plecia. Odkedy ti na nich stojí je už všetko v pohode.)
Vašou úlohou je vypísať hmotnosti artistov v takom poradí, v akom majú vytvoriť vežu, ktorá nespadne.
Príklad
Vstup
N=5
62
70
55
68
56
Výstup
70
68
62
56
55
2. Zábava na kolieskach...
(15 bodov)
"Inline hýbe svetom." To si jedného krásneho letného dňa povedal aj Janči a rozhodol sa, že namiesto skvéleho nového harddisku investuje radšej do zdravia a kúpi si korčule. I zavolal kamaráta Ferka a vybrali sa korčule kupovať. Asi týždeň veľmi iniciatívne pobehovali po rôznych obchodoch so športovými potrebami a pozerali na korčule... tvrdosť, materiál, typ, tvar a polomer koliesok, typy ložísk, veľkosť topánky. Poznáte to, s obchodmi je to ťažké... tak veľa tovaru, tak málo času a ešte menej peňazí. Nakoniec sa podarilo. Kúpili krásne, veľké, čierne korčule.
Problémov bolo, samozrejme, veľa, no niekde začať treba. Korčule už máme, ešte sa tak naučiť korčuľovať. I povedal si Janči, že ak sa má dolámať, tak určite skôr, než sa mu Marienka z dovolenky prinavráti. Vzal korčule a tadá na najbližšiu asfaltovú plochu. Obul korčule. "Pravá noha..., ľavá noha..." -- a čo nezistil? "Ono to ide! ... Hmmm... ešte tak zistiť, ako sa na tom pekelnom stroji brzdí?!?!? Aha strom!"
Netrvalo dlho a... Nie, nedolámal sa. To by ste chceli, čo?! Vy mrchy jedny škodoradostné! Neverili by ste, ale napriek svojmu pokročilejšiemu veku sa naučil korčuľovať pomerne rýchlo. Objavil sa však problém druhý. Pri športe (a iných zábavných činnostiach) človek rýchlo stráca pojem o čase, a navyše veľmi rýchlo vyhladne. Začína sa stmievať a Janči s hrôzou v očiach zisťuje nepríjemnú skutočnosť: obed už asi nestihne. No predsa len je tu ešte nejaká šanca stihnúť aspoň večeru... ale to by sa musel poriadne poponáhľať (aby mu doma všetko nepojedli).
Janči -- ako každý správny nezodpovedný živel -- nemá "bledomodrý" šajn, kadiaľ sa rýchlo dostane domov. A preto ste tu vy, ktorí ochotne zachránite úbohý ľudský život pred smrťou hladom.
Úloha
Na vstupe máme zadané dve celé čísla N a M a potom mapu rozmerov N riadkov po M stĺpcoch. Miesto, kde sa Janči práve nachádza je označené znakom "J", miesto, kde býva, je označené "D". Cestičky, po ktorých sa môže pohybovať sú označené znakmi "." a naopak, miesta, kadiaľ sa korčuľovať nemôže, znakmi "#". Mimo mapy sa taktiež pohybovať nemôže. Janči je po celom dni značne unavený, a teda od neho nemôžete chcieť, aby nebodaj menil rýchlosť -- vlečie sa teda stále rovnako rýchlo. Vašou úlohou je nájsť čo najkratšiu (a teda aj najrýchlejšiu) cestu, ako sa môže dostať domov (môže sa pohybovať všetkými 8 smermi).
Príklad
Vstup
N=12, M=31
############################### #.......#######..##..##..##...# #.#####.#######..##..##..##...# #.####..########.............## #.#####.########.###########D## #..###........##..##.##.####.## ##.####.##.##............###..# ##.###########.########.#####.# ##.............########..####.# #.J.##..##..##..#######.#####.# #...##..##..##..#######.......# ###############################
Výstup
############################### #.......#######..##..##..##...# #.#####.#######..##..##..##...# #.####..########.----------\.## #.#####.########/###########D## #..###........##|.##.##.####.## ##.####.##.##../.........###..# ##.###########/########.#####.# ##.----------/.########..####.# #.J.##..##..##..#######.#####.# #...##..##..##..#######.......# ###############################
(Cestu nemusíte vykresľovať tak pekne ako my v príklade, stačí ľubovoľne vyznačiť políčka, kadiaľ vedie.)
3. Zaľúbený čaj
(15 bodov)
"Mňam, ten môj čaj je taký dobrý!" rozplýva sa Majka.
"Máš pravdu Majka, aspoň o sto lepší ako môj." súhlasí natešený Mirko.
Mirko a Majka si vždy radi pochutnajú na dobrom čaji. Nedávno Mirko zistil, že čaj je oveľa lepši, ak doňho pridá špeciálnu čajovú hubu. V zelenom čaji sa taká huba dokonca aj rozmnožuje, každý deň, o šiestej poobede, sa premení každá huba na nové tri. Tento proces sa opakuje až kým niekto čaj nevypije. Samozrejme, čím viac húb, tým viac chute. Ako správny milovník čajov, používa Mirko vlastnú stupnicu chute čaju. Po niekoľkých ochutnávkach už vie, že každá huba zvýši stupeň chuti čaju o jedna. A navyše, ako správny milovník čajov, používa rovnakú stupnicu aj pre svoju lásku k druhým.
Mirko má Majku rád, aj vie presne stupeň svojej lásky. Mirko je ale hanblivý, preto sa rozhodol, že ju zatiaľ len pozve na svoj nový čaj. Ale predsa len by jej nejako chcel naznačiť svoje pocity. Zaumienil si teda, že Majkin čaj spraví lepší od vlastného. Aby mohla vytušiť, ako ju má rád, bude rozdiel stupňov chutí ich čajov rovný stupňu Mirkovej lásky k Majke.
Mirko teda musí začať pripravovať dva čaje, na ktorých si s Majkou o niekoľko dní o piatej pochutnajú. Húb má ale obmedzenú zásobu, každý deň môže použiť naviac jednu. Nevie ale, do ktorého čaju ju má kedy pridať (ak vôbec). A stačí mu tých niekoľko dní aby spravil dosť chutný čaj?
Úloha
Vašou úlohou je napísať plán pre Mirka. Na vstupe sú dve celé čísla, L -- stupeň Mirkovej lásky k Majke a M -- počet dní ostávajúcich do ich stretnutia. Plán bude M celých čísel, buď -1, 0 alebo 1. Číslo na i-tom mieste Mirkovi povie, do ktorého čaju pridá hubu v i-ty deň. Nula znamená že do žiadneho, -1 do svojho a 1 do Majkinho čaju. Huba vložená v i-ty deň sa v čaji potom (M-i) krát rozdelí na tri, t.j. čaju pridá 3(M-i) chute. Rozdiel medzi výslednými chuťami Mirkovho a Majkinho čaju musí byť práve L. V prípade že nie je možné čaje do M dní dostatočne ochutiť, treba to Mirkovi čo najmiernejšie oznámiť.
Príklad
Vstup #1
7 58
Výstup #1
0 0 1 -1 0 1 1
Vstup #2
4 81
Výstup #2
Prepáč Mirko, ale čaje už nestihneš pripraviť.
(Poznámka: V prvom príklade z huby, ktorú vhodí do Majkinho čaju na tretí deň, bude na konci 34=81 chute. Z huby zo šiesteho dňa budú 3, zo siedmeho 1 chuť. v Mirkovom čaji bude z huby zo štvrtého dňa 33=27 chute. Nakoniec teda bude rozdiel medzi chuťami čajov (81+3+1)-(27)=58.)
4. Zzzzzz alebo imatrikulácia
(15 bodov)
Imatrikulácia je (aspoň na vysokej škole) úžasná slávnosť---pekne napochodujete podľa abecedy, sľúbite, že budete vzornými študentmi, prevezmete imatrikulačný list, pokloníte sa rektorovi (podaktorí to spackajú a poklonia sa študentom) a odpochodujete. Keď je tých študentov trošku viac (a na vysokej ich je trošku viac), je to prudká zábava. Sedíte na svojom mieste (tí prezieravejší si priniesli nejakú literatúru) a čakáte, kým príde rad na vás (teda na teba, lebo ja vám tykám). Tí, čo túto procedúru úspešne absolvujú, môžu až do samého konca -- ktorý je zdanlivo v nedohľadne -- spať. Na druhej strane tí, čo ešte len majú ísť, sa musia sústrediť, aby nebolo dáke fiasko. Po chvíli ľudia s menami ku koncu abecedy začnú presviedčať ostatných, aby sa navrhlo nejaké spravodlivejšie poradie. Tu však vzniká problém: podľa niektorých by bolo najspravodlivejšie začať od konca -- veď "vždy" sa začína od začiatku; na druhej strane, ľudkovia s priezviskami na začiatku abecedy horlivo protestujú: "veď práve, vždy sa chodí podľa abecedy, nás ako prvých vyvolávajú k tabuli, vtedy vám to vyhovuje, čo?"; ďalšia skupinka chce zase začať od stredu... A tak začala hara-vara.
Čas pokročil a viacerí zistili, že takto to asi nepôjde, a že najspravodlivejšie (resp. jediné) poradie, na ktorom sa budú schopní dohodnúť, bude asi náhodné. Nuž ale kde by nabrali toľko slamiek? A kým by sa podľa slamiek zoradili... Našťastie sú tu KSP-áci, ktorí im s radosťou napíšu program, ktorý nejaké náhodné poradie vygeneruje, však?
Úloha
Na vstupe je zadané kladné celé číslo N. Úlohou je vypísať čísla od 1 do N v náhodnom poradí. Každé poradie má mať rovnakú pravdepodobnosť. To znamená, že keby sme váš program spustili 100.N! krát, každé poradie by sa malo na výstupe objaviť približne stokrát.
Príklad
Vstup
N = 3
Výstup
1 2 3 alebo
1 3 2 alebo
2 1 3 alebo
2 3 1 alebo
3 1 2 alebo
3 2 1 s rovnakou pravdepodobnosťou
5. Zase škola
(15 bodov)
Škola vám už dávno začala a nám pomaly ale isto začal nový semester. Taký začiatok semestra so sebou prináša veľa úloh ako napr. zápis, vymyslenie novej série KSP-čka, ale hlavne vytvoriť si rozvrh. Matfyzáčka Monika si pozapisovala všetky predmety zo svojho ročníka a ešte polovicu nasledujúceho. Pozrela sa na svoj rozvrh a zhrozila sa. Nielenže musí každé ráno skoro vstávať, ale hlavne musí byť na dvoch a niekedy až na troch prednáškach naraz. To jej však až tak nevadí. Vyberie si jednoducho ten zaujímavejší predmet, na ktorý bude chodiť a na ostatné má do skúšky veľa času.
Teraz má však väčší problém. Chcela by sa pochváliť ostatným, koľko toho za semester stihne. Preto potrebuje svoj rozvrh nejakým spôsobom nakresliť a ukázať ostatným. Tu však potrebuje vašu pomoc. Pomôžte Monike nakresliť si svoj rozvrh prehľadne, aby sa v ňom vyznala a pritom efektne, aby mohla zapôsobiť na ostatných.
Úloha
Vašou úlohou je napísať program, ktorý na vstupe dostane popis Monikinho rozvrhu a vypíše ho v nejakom peknom a prehľadnom tvare. Na vstupe dostanete zoznam jednotlivých predmetov. O každom predmete dostanete 5 údajov: jeho názov, typ, deň, čas a miestnosť konania. Názov je reťazec dlhý maximálne 40 znakov. Typ predmetu je napr. prednáška, cvičenie, kurz, laboratórne cvičenie atď. a má maximálne 20 znakov. Všetky predmety začínajú a končia v 50 minútových intervaloch od 8:10 do 19:50. Miestnosť je reťazec dlhý maximálne 5 znakov. Časy predmetov sa môžu ľubovolne prekrývať. Formát vstupu si môžete zvoliť ľubovolný, aký vám vyhovuje.
Rozvrh kreslite do textového režimu, aby si ho mohli prečítať aj ľudia pracujúci na starých termináloch, ktoré nemajú grafický režim. Rozvrh by nemal byť príliš dlhý ani široký, aby sa zmestil na obrazovku resp. aby sa dal vytlačiť na jeden list papiera. Hodnotiť sa bude hlavne prehľadnosť rozvrhu a jeho vzhľad.
Okrem samotného programu nám pošlite aj niekoľko príkladov rozvrhov, ktoré váš program vygeneroval.
Príklad
Vstup
Utorok, 8:10-10:40, Úvod do distribuovaných algoritmov, Prednáška, C
Piatok, 8:10-10:40, Teória paralelných výpočtov, Prednáška, B
Výstup
Pondelok Utorok Streda Štvrtok Piatok
========================================================================
8 10 > |p C| | |p B|
|Úvod do | | |Teóri.paral.|
-------------------|distr.algor.|------------|------------|výpočtov |
9 00 > | | | | |
| | | | |
-------------------| |------------|------------| |
9 50 > | | | | |
| | | | |
-----------------------------------------------------------------------|
© KSP, 2. september 2004, webmaster
