- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Príklady 1. kola letnej časti 22. ročníka KSP-Z
A sú tu nové zadania/vzoráky (nehodiace/hodiace sa škrtnite/zakrúžkujte) 1. kola letnej/2. kola zimnej série -/kategórie Z vášho ne/- obľúbeného seminára KMS/FKS/KSP/WTF. Nezabudnite/nezabudnite/naozaj nezabudnite prečítať si pravidlá a poslať nám svoje riešenia (a pár poštových/psích známok) do 4. marca 2005. Ostrieľaní riešitelia pozor, je to piatok, nie pondelok!
KSPáci
- Zažite hrôzu v knižnici!
- Zmenený zákon
- Zelený stôl
- Zaujímavá permutácia
- Zvítanie so zelenými mužíkmi...
1. Zažite hrôzu v knižnici!
(15 bodov)
Jožko Marhuľa zhrozene vpadol do miestnej pobočky mestskej knižnice v Trebuliakove (inak známej ako MiePoMesKnivTreb). Iba dnes sa dozvedel, že do zajtra má prečítať "perlu slovenskej literatúry", ktorú mu zadala jeho učiteľka slovenčiny. V MiePoMesKnivTreb sa ocitol po prvý raz a z jedovatej vône plesnivejúcich kníh sa mu okamžite zakrútila hlava. Bolo mu jasné, že zlovestne vyzerajúca knihovníčka (mala iba 537 vlasov a 1 kolozub), mu nepomôže, ba naopak... Beštiálna bytosť za pultom sa usmiala, akonáhle Jožko vyjachtal svoju opovážlivú prosbu, a jej kolozub sa pritom zaleskol v slabom svetle jedinej stropnej lampy. Jožko nasucho preglgol, keď vyziabnutý hnát s nechtom pripomínajúcim pazúr ukázal na temne týčiace sa regály kníh. Zdalo sa mu, že sa tiahnu do nekonečna (alebo aspoň tak ďaleko, že sa ich koniec blížil limitne k nekonečnu).
Knihovníčka si udržiavala celú knižnicu usporiadanú -- avšak nie podľa mien autorov alebo podľa názvu knihy, ale podla nejakých divných čísel. Pokiaľ chcel niekto nejakú knihu, mohol si ju sám nájsť alebo tejto bytosti povedať číslo knihy (lebo inak by ju asi ani sama nenašla). Jožko sa poobzeral a usúdil, že by bolo veľmi nebezpečné vybrať sa medzi regále a hľadať svoje knihy, ktoré sa nachádzajú nevedno ako ďaleko. Mohlo by sa mu stať, že zablúdi a bude večne blúdiť regálmi alebo dokonca ho mohla nejaká kniha aj zjesť! Preto sa odobral ku kartotéke a poďho hľadať, aby svojej knihy číslo čo najskôr našiel a stihol ju do zajtra prečítať. Kartotéka (abecedný zoznam kníh) je však obrovská a tiež to nie je len tak ľahké hľadať. Rovno mohol zabudnúť na to, že prejde všetky záznamy. To by tu mohol zostať až do zajtrajšieho dna a to už bude neskoro! Preto mu pomôžte rýchlo nájsť číslo jeho knihy!
Úloha
Predpokladajme, že v programe máte pole veľkosti N (môže byt veľmi veľké), ktoré predstavuje kartotéku s N knihami. Pre každú knihu je tu záznam: meno (text pozostávajúci s veľkých a malých písmen abecedy, čísel a medzier) a číslo knihy (celé a jedinečné). Toto pole je utriedené podla názvu knihy. (Vo vašom programe obsah tohto poľa samozrejme musíte po spustení odniekiaľ načítať. Nás však zaujíma len tá časť programu, ktorá bude v už načítanom poli vyhľadávať.) Na vstupe dostanete názov hľadanej knihy. Vašou úlohou je navrhnúť algoritmus, ktorý čo najrýchlejšie nájde knižničné číslo danej knihy. Váš algoritmus by mal fungovať všeobecne pre ľubovoľný názov knihy. Pokiaľ záznam pre knihu nájdete, vypíšte jej číslo, inak vypíšte, že sa kniha v knižnici nenachádza.
Príklad
Vstup #1
Kartotéka:
Arabela 112
Popoluska 158
Pysna princezna 155
Sipova Ruzenka 150
Snehulienka a 7 trpaslikov 999
Zlatovlaska 120
Otázka:
Snehova kralovna
Výstup #1
Kniha sa v knižnici nenachádza.
Vstup #2
Kartotéka:
Arabela 112
Popoluska 158
Pysna princezna 155
Sipova Ruzenka 150
Snehova kralovna 33
Snehulienka a 7 trpaslikov 999
Zlatovlaska 120
Otázka:
Snehova kralovna
Výstup #2
33
2. Zmenený zákon
(15 bodov)
"No to snáď nie je pravda! Oni ten zákon zase zmenili!" povzdychol si Pedro. O čomže to hovorí? Nuž, o najnovšom vylepšení zákona o daniach v Zimbabwe. Doteraz bolo vyplňovanie daňového priznania veľmi jednoduché -- stačilo len vymenovať v chronologickom poradí všetky príjmy, ktoré človek v daný rok mal. Pedro si presne takéto záznamy viedol počas celého roka a už sa tešil, že konečne raz bude mať to priznanie rýchlo vybavené a bude sa môcť zaoberať zaujímavejšími vecami. No a zrazu takáto pohroma!
Nový zákon nariaďuje, že príjmy musia byť usporiadané najprv podľa druhu činnosti, z ktorej pochádzajú, a to v abecednom poradí! Tak napríklad, ak trinásteho mája zarobil tisícku za prenájom automobilu a pätnásteho januára prenajal vŕtačku, tak príjem z automobilu má byť uvedený skôr, ako príjem z vŕtačky; napriek tomu, že ten druhý bol uskutočnený skôr. Keďže chudák Pedro má toho na robote ešte strašne veľa, požiadal o pomoc vás -- skúsených programátorov. Pomôžete mu?
Úloha
Máte zadané číslo N, ktoré označuje celkový počet príjmov, ktoré Pedro za uplynulý rok mal. Okrem toho máte zadaných N dvojíc "názov činnosti" a "príjem" (t.j. Pedrov zoznam, ktorý je v chronologickom poradí). Vašou úlohou je usporiadať tieto záznamy do abecedného poradia tak, že v rámci jedného názvu činnosti musí zostať zachované chronologické poradie.
Príklad
Vstup
N=5
Vrtacky 40
Automobily 2000
Motorky 1000
Automobily 1000
Automobily 1500
Výstup
Automobily 2000
Automobily 1000
Automobily 1500
Motorky 1000
Vrtacky 40
3. Zelený stôl
(15 bodov)
"Tentoraz nemáš šancu!", prehodil vypasený kšeftár Mrľa a so záujmom pozeral na mladého, urasteného mládenca, čo len včera bol prichodil do mesta. Mladému sa leje pot z čela, poškuľuje, všelijako sa mrví, ale vie, že nakoniec aj tak bude musieť udrieť. Už to nechce odkladať. Zavrie oči a BUM!
Keď ich znova otvorí, pozrie najprv na zdeseného Mrľu, vypliešťajúceho oči na stôl. Pozrie tam i on. Podarilo sa! Všetky štyri gule ostali v rohoch stola (Biliardový stôl nemá diery). Vykročí ku kšeftárovi. "A teraz peniaze", povie. Mrľa sa zdráha, vyhovára, ale veľmi si nepomôže, mladík by ho raz dva premohol. Vtom ho osvieti. Povie: "Urobíme poslednú stávku, ak vyhráš, dostaneš všetko, na čo len pomyslíš. Ak prehráš, nechám ťa vyváľať v bahne a oberiem ťa do poslednej vindry. Ber, alebo nechaj tak!" Mladík je prostý, je to chlapec z dediny, neuvedomí si, že už vyhral dosť a stávku prijme.
"Tak teda počúvaj", Mrľa si odkašle a poodhalí všetkých svoji dvanásť žltých zubov, "Guľu dáme do stredu stola. Chcem, aby sa toľko a toľkokrát odrazila od dlhšej strany, toľko a toľko od kratšej a nakoniec sa zastavila v strede stola." "Koľko?", pýta sa neveriacky mladík. "Toľko a toľko", zopakuje tučniak s diabolským úškrnom na tvári.
Hoci náš mládenec je veľký hráč biliardu, rozmýšľanie mu vždy skôr nešlo, ako išlo. Preto by potreboval vašu pomoc, aby vedel kam má guľu poslať.
Úloha
Na vstupe sú zadané a, b, kde a je dĺžka strany stola rovnobežnej s barpultom, b je dĺžka tej druhej strany. Ďalej je zadané n, m, pričom n je požadovaný počet odrazov od strany dĺžky a a m od strany dĺžky b.
Ak si biliardový stôl predstavíme ako súradnicovú sústavu so stredom stola v jej počiatku, tak chceme nájsť priamku, po ktorej treba poslať guľu. Vypíšte uhol v stupňoch medzi touto priamkou a x-ovou osou (t.j. osou rovnobežnou s barpultom). Guľa musí zastať opäť presne v strede stola. Môžete sa spoľahnúť, že mladík pošle guľu správnou rýchlosťou.
Príklad
Vstup
100.0 100.0 1 1
23.4 14.8 33 22
13.45 800.0 15 1900
Výstup
45.023
43.515
25.166
4. Zaujímavá permutácia
(15 bodov)
"Zjem index, ak toto nie je tá Zaujímavá permutácia!" nechal sa včera počuť Onot. Ykborh sa už chystá do školy. Ak Onot nenájde trojčlennú aritmetickú postupnosť, mal by mu aspoň kečup doniesť, aby sa mu lepšie prehĺtalo. Onot je šikovný a snaživý, ale čo ak nemá šancu?
Úloha
Je dané číslo N a tiež permutácia (postupnosť N čísel, v ktorej sa každé z čísel 1, ..., N vyskytuje práve raz) čísel 1, ..., N. Poraďte Onotovi, či sa dá z tejto permutácie N-3 čísel vyškrtnúť tak, aby zvyšné tri (v poradí, v akom boli v pôvodnej permutácií) tvorili aritmetickú postupnosť.
Ešte raz to isté matematicky: Zistite, či existujú také čísla i<j<k, že postupnosť (pi, pj, pk) je aritmetická. (Postupnosť je aritmetická, ak existuje číslo d také, že každý ďalší člen dostanem z predchádzajúceho pripočítaním d. V našom prípade teda musí platiť pi+d=pj a pi + 2 . d=pk.)
Príklad
Vstup
N=6 4 5 3 6 1 2
Výstup
áno
(Poznámka. Trojica (5, 3, 1) tvorí aritmetickú postupnosť s diferenciou -2.)
5. Zvítanie so zelenými mužíkmi...
(15 bodov)
Aj toto sú životné situácie, na ktoré sa musíme prichystať. A ideálne je prichystať sa poriadne. Nikto nevieme, ako vyzerajú, kde sa schovávajú. Možno sú už medzi nami! V každom prípade, budme k nim milí, pekne a milo ich privítajme. A čo už je milšie ako... kvetinky. Krásne, zelené lístky so žltým koláčom. Hotové ICQ.
Máme hriadku so štvorcovými políčkami, do každého políčka môžeme zasadiť najviac jeden kvietok. Čo chceme robiť, je kresliť si čiary z kvietkov. Keď k nám budú prilietať, nech už z dialky vidia, že ich máme radi. Ale samozrejme, aj my máme len obmedzené prostriedky. Nikto nevieme, či vôbec sú, a či príjdu. Takže v podstate zbytočne vyhodené peniaze. Chceme ich, aby vyzerali čo najlepšie, no nemáme na ne prostriedky. A navyše, budú to sadiť záhradníci. Teda čím jednoduchšia matematika, tým lepšie, a tým skôr to bude zasadené.
Úloha
Dostaneme rozmer hriadky N riadkov, M stĺpcov a potom niekolko riadkov obsahujúcich súradnice koncových bodov čiary (X1, Y1 X2, Y2). Výstupom je bitmapa s nakreslenými čiarami.
Príklad
Vstup
N=10, M=20
2,2 5,5
10,2 8,6
11,6 19,4
Výstup
.................... .*.......*.......... ..*.....*........... ...*....*.......***. ....*..*.....***.... .......*..***....... .................... .................... .................... ....................
© KSP, 7. február 2005
