- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Príklady 2. kola letnej časti 20.ročníka KSP-Z
Milé deti,
Školský rok sa nám pomaly chýli ku koncu, nás už trápia skúšky, niektorých z vás práve týrajú na maturách... a všetci spolu sa tešíme na prázdniny. Nebojte sa, nie je to už ďaleko. Už vás od prázdnin delí len jedna séria KSP. Tak hor sa do riešenia!
Svoje riešenia nám posielajte do 23. júna 2003 a nezabudnite priložiť známky v hodnote 15 Sk,-. Ešte by sme chceli upozorniť hlavne riešiteľov z GJH, že riešenia, ktoré sa ku nám nedostanú načas, nebudú opravené.
KSPáci
1. Zas.... chodník
(15 bodov)
Neviem, či sa vám to už stalo, ale ja teraz stojím na začiatku chodníka, kade sa prehnalo stádo kráv. Zjavne sa im zdal nanajvýš vhodným miestom, kde môžu odľahčiť svojmu komplikovanému tráviaceme ústrojenstvu. Prejsť po takomto chodníku nie je nič príjemné, preto som si vymyslel zabavku.
Chcem preskákať pomedzi lajná tak, aby som vždy prekročil práve jedno. A aby som nemal dilemu, kde mám presne stúpiť, pôjdem stále rovno (tým istým smerom ako doteraz) a budem robiť všetky kroky rovnako dlhé.
Úloha
Predstavme si, že náš chodník tvorí kladnú x-ovú poloos, stojím v nule. Na chodníku leží N lajen, každé zaberá nejaký neprázdny otvorený interval. Pre každé z nich sú dané dve čísla, určujúce kde začína a kde končí. Lajná sa navzájom neprekrývajú a zadané sú v poradí odo mňa, t.j. prvé je najbližšíe. Každým krokom chcem prekročiť práve jedno lajno. Vašou úlohou je nájsť takú dĺžku mojho kroku, aby sa mi ich podarilo spraviť čo najviac.
Príklad
Vstup
N=4
(2.0, 4.0), (6.0, 6.7), (8.8, 11.3), (12.4, 17.9)
Výstup
krok=4.1
(Prvé tri kroky sú OK, štvrtým sa mi už nepodarí štvrté lajno prekročiť.)
2. Závažný problém
(18 bodov)
Ako isto viete, prednedávnom sa skončilo IPSC. IPSC je internetová súťaž tímov v riešení problémov. Je zadaných niekoľko úloh a ku každej úlohe existujú dva vstupy – ľahký a ťažký vstup. Tímy musia vyriešiť zadaný problém a odovzdať korektné výstupy k daným vstupom. Tie potom špeciálny program – testovač skontroluje a vytvorí "log". Log je súbor, v ktorom sú uložené údaje o jednotlivých pokusoch tímov o riešenie daného problému. Ďalší program si z logu zistí, aké problémy vyriešili jednotlivé tímy a vygeneruje výsledkovú listinu. Ale tu nastal závažný problém – tento program bol príliš pomalý. A tak by ste nám mohli napísať rýchlejší.
Každý riadok logu obsahuje informácie o jednom pokuse o odovzdanie výstupu, volanom tiež "submit". Riadky sú samozrejme zotriedené vzostupne podľa času odovzdania. O každom submite sú v logu 4 údaje – čas, kedy bol daný submit odovzdaný, meno tímu, ktorý daný submit odovzdal, meno príkladu a výstup z testovača. Čas odovzdania príkladu je celé číslo od 1 do 2000 a je to počet minút od začiatku súťaže. Meno tímu je ľubovoľný reťazec tvorený maximálne 20 písmenami anglickej abecedy bez medzier. Meno príkladu sa skladá z jedného znaku a jedného čísla. Znak je písmeno od A po H, ktoré určuje problém, ktorého je to submit. Číslo môže byt buď 1 alebo 2. Ak je to 1, tak je to výstup k ľahkému vstupu, ak je to 2, tak ku ťažkému. Čiže napríklad C1 znamená, že je to výstup na ľahký vstup problému C. Výstup z testovača je ľubovoľný reťazec dĺžky najviac 30 začínajúci písmenom. Ak je to reťazec 'OK' (bez apostrofov), znamená to, že uvedený výstup je správny, inak je nesprávny a tento reťazec udáva druh chyby.
Bodovanie: Za každý správne vyriešený ľahký vstup získa tím jeden bod, za každý správne vyriešený ťažký vstup získa tím dva body. Ak má viacero tímov rovnaký počet bodov, o ich poradí rozhodnú trestné minúty. Tím s menším počtom trestných minút sa umiestni na lepšom mieste ako tím s väčším počtom trestných minút. Trestné minúty sa získavajú nasledovne: Za každý správne vyriešený ľahký vstup sa k doterajším trestným minútam tímu pripočíta čas submitu, kedy ho odovzdal a ešte 10-násobok počtu predchádzajúcich nesprávnych submitov tohto vstupu. Za každý správne vyriešený ťažký vstup sa k doterajším trestným minútam tímu pripočíta čas submitu, kedy ho odovzdal a ešte 20-násobok počtu jeho predchádzajúcich nesprávnych submitov. (Ak sa tímu nepodarí správne vyriešiť nejaký vstup, tak za neho nedostane žiadne trestné minúty.) Ak sa tím pokúsi znovu vyriešiť už ním vyriešený problém, tak sa tento pokus berie ako nesprávny, ale tím nedostane za neho žiadne trestné minúty navyše. Ak má viacero tímov rovnaký počet bodov aj trestných minút, tak sa umiestnia na rovnakom mieste a je jedno ako sú zoradení.
Úloha
Vašou úlohou je napísať program, ktorý z daného logu vygeneruje výsledkovú listinu. V nej budú tímy utriedené od prvého po posledného. Pre každý tím bude v nej vypísané jeho umiestnenie, počet bodov, mená problémov, ktoré vyriešil a jeho počet trestných minút.
Príklad
Vstup
100 MojTim A2 Zle 137 TvojTim A1 OK 189 MojTim A2 OK 290 TvojTim C1 Malo cokolady 591 MojTim A2 Uz vyriesene 630 TvojTim C1 OK 780 JehoTim F1 zle 800 JejTim C2 Privela cokolady
Výstup
Por. Tim body cas priklady
1. MojTim 2 189 A2
2. TvojTim 2 777 A1 C1
3. JehoTim 0 0
JejTim 0 0
3. Zase neporiadok
(15 bodov)
Rodičia si stále myslia, že deti majú vo svojich veciach neporiadok. V podobnej situácii je aj Riško. Napríklad aj teraz mu na stole leží kopa nesmierne dôležitých krabíc. Ale vysvetlite mame, že sú dôležité! Márna snaha, musia preč. Lenže to nie je také jednoduché. Krabice sú ťažké a preto sa dajú premiestňovať iba po jednej. Navyše tá kopa krabíc je vlastne veža z rôzne veľkých krabíc, pričom vždy je menšia krabica na väčšej. Toto usporiadanie je dôležité, lebo keby sa položila väčšia krabica na menšiu, tá menšia by sa rozpučila. Izba je takmer plná haraburdia, sú tam len dve voľné miesta – v rohu izby a v skrini. Na každé z nich by sa veža z krabíc tak akurát vošla. Nuž a na jedno z nich (je jedno ktoré) musí Riško vežu krabíc presunúť.
Časom zistil, že najrýchlejšie sa to dá takto: Upratujeme v ťahoch. Keď robíme nepárny ťah, presunieme najmenšiu krabicu, a to nasledovne: Ak bola na stole, dáme ju na vrch veže v rohu izby, ak bola v rohu izby, dáme ju do skrine a ak bola v skrini, pôjde na stôl. A keď robíme párny ťah, presunieme krabicu, ktorá nie je najmenšia. (To sa dá spraviť len jedným spôsobom.)
Aby však Riško neprehadzoval krabice nadarmo, potreboval by si overiť, či tento spôsob funguje. Potreboval by program, ktorý mu pre dané t povie, ako budú vyzerať tie 3 veže z krabíc (kopa na stole, v rohu izby a v skrini) po vykonaní t ťahov.
Úloha
Dané sú prirodzené čísla N, t. N je počet krabíc, ktoré treba upratať. Krabica číslo 1 je najmenšia, N je najväčšia. Sú 3 veže z krabíc, na začiatku sú všetky krabice na prvej v poradí (zdola) N,N-1,...,1, zvyšné dve veže sú prázdne. Určte, ako budú vyzerať veže po vykonaní t ťahov postupu popísaného vyššie.
Príklad
Vstup
N=3, t=4
Výstup
1. veža: prázdna
2. veža: 3
3. veža: 2 1
4. Zo sna hovoriaci čarodej
(15 bodov)
Život je plný stereotypov. Jedným z najklasickejších je starý čarodej. Dňom i nocou sa venuje výskumu mágie, ktorá je nad úrovňou nás – prostých ľudí. Je v podstate milý a príjemný, kým mu neprekážate, nič po ňom nechcete a nevyrušujete ho od práce. V opačnom prípade vie byť naozaj veľmi nepríjemný.
Žiť v jednom dome s takýmto čarodejom nie je žiadna radosť. Vždy keď si sadáte, musíte sa poriadne pozrieť kam, lebo napríklad prisadnutý bazilišok vie byť veľmi nepríjemný a ak rozsadnete pavúka, čarodeja naštvete, lebo určite práve potreboval nejakého živého. Po dome sa povaľuje neuveriteľná kopa rôznych kníh, zvitkov, fľaštičiek s rôznofarbnými tekutinami a ponožiek. A to už nehovorím o tom, čo sa stane, ak niektorú z fľaštičiek rozbijete alebo božechráň sa z nej napijete.
Malý Garak, Belsambarov učeň, dnes oslavuje svoje desiate narodeniny. Keď zoberieme do úvahy všetky spomínané nepríjemnosti, ktoré sa môžu človeku v takom dome pritrafiť, je to až prekvapivé. Náladu mu však dnes kazí nová nepríjemnosť, ktorá ho čaká. Belsambar totiž začal rozprávať zo sna a často sa mu podarí vysloviť nejaké zaklínadlo. Garak už vie rozpoznať zaklínadlo od obyčajného mrmlania, ale je príliš pomalý. Potreboval by pomoc od počítača.
Slovo je zaklínadlo práve vtedy, keď spĺňa nasledujúce podmienky:
- jeho dĺžka je deliteľná magickým číslom 3
- obsahuje ako podreťazec kúzelnú formulu "abraka"
- neobsahuje f, c ani dve samohlásky za sebou
Napíšte program, ktorý Garakovi pomôže rozhodnúť, či je dané slovo zaklínadlo. Program musí byť samozrejme čo najrýchlejší, ale najdôležitejšie je aby potreboval čo najmenej pamäte (a dal sa spustiť na Garakovom prastarom počítači).
Príklad
Vstup
abrakadabra bezvysypattiesmeti vrakadrakabrakarak
Výstup
NIE NIE ANO
5. ZJEDZ OBED HARRY
(15 bodov)
Takýto čudný odkaz si našiel Harry na posteli vo svojej komôrke. Najprv si myslel, že sa ho spriatelený domáci škriatok snaží uprozorniť na jeho nezdravé stravovacie návyky. Potom si však uvedomil, že u nich žiadny škriatok nebýva. Navyše, keď sa lepšie prizrel, všimol si, že medzi prvými dvoma slovami je akýsi malý krížik a medzi druhým a tretím sú zase dve krátke čiarky (aby ste si to vedeli predstaviť, vyzeralo to takto: ZJEDZ + OBED = HARRY). Vtom mu napadlo -- veď je to list od Hermiony! Ešte v škole sa dohodli, že všetky správy, ktoré si pošlú, budú pre istotu magicky šifrovať. Čudný nápis je len zámok a skutočná správa sa ukáže iba tomu, kto ho dokáže odomknúť magickým kľúčom. Ten vyzerá ako zoznam dvojíc písmenko=číslica, pričom žiadne písmenko ani číslica sa v kľúči neopakuje. Odomykanie vyzerá tak, že sa v zámku písmenká nahradia podľa kľúča číslicami. Zámok sa otvorí, ak po tomto nahradení výsledná rovnosť platí.
Teraz však Harry stojí pred ťažším problémom -- potrebuje Hermione napísať odpoveď a ako na potvoru nevie vymyslieť žiadny magický zámok. Pomôžete mu?
Úloha
Vašou úlohou je napísať program, ktorý na vstupe nedostane vôbec nič a na výstup vypíše nejaký zámok. Zámok sa skladá z niekoľkých zmysluplných slov oddelených matematickými operátormi `+', `-', `*', `/' a `='. Samozrejme je nevyhnutné, aby k tomuto zámku existoval nejaký kľúč, ktorý ho odomkne. Na druhej strane, správnych kľúčov by malo existovať čo najmenej, ideálne jediný. Spolu s programom nám pošlite aspoň tri najzaujímavejšie zámky (aj s kľúčmi), ktoré váš program vytvoril.
Poznámka
Ak váš program používa nejaké rozsiahle pomocné dáta (napríklad zoznam slovenských slov), tak tie nám posielať nemusíte, stačí ak popíšete, čo sú zač.
Príklad
ZJEDZ + OBED = HARRY (A=0 E=1 Y=2 O=3 D=4 B=5 R=6 J=7 Z=8 H=9) BABKA + K + BABCE + BUDU = KAPCE (B=1 P=2 K=3 E=4 D=5 C=7 A=8 U=9) MICRO + SOFT = SMELL (E=0 O=1 F=2 R=3 T=4 L=5 M=6 S=7 I=8 C=9) AKO + SA + DO + HORY = VOLA (R=0 D=1 H=2 V=3 S=4 L=5 Y=6 O=7 K=8 A=9) TAK + SA + Z + HORY = OZYVA (O=0 Y=1 V=2 H=3 Z=4 K=5 R=6 S=7 A=8 T=9) UNIX + ADMIN = FRIEND (F=0 I=1 N=2 U=3 A=4 R=5 X=6 M=7 D=8 E=9) DAJ * MI = JEST (A=0 M=1 D=2 J=3 S=5 T=7 E=8 I=9) HACK * THE = PLANET (N=0 H=1 A=2 L=3 T=4 P=5 E=6 C=7 K=9)
Poznámka
Všimnite si, že nám nevadí, že v niektorých prípadoch začínali čísla nulou.
(c) 26. mája 2003 webmaster
