Milí riešitelia!
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!
(15 bodov)
Určite ste už počuli o tajomnom Belgaratovi. Áno, je to ten Belgarat, ktorý privodil skazu celému východnému Anghornu. Tak práve tento Belgarat raz zavítal na dvor kráľa Forna, keď ho hľadanie mocného artefaktu zavialo do týchto končín. Ako to už v podobných príbehoch býva, vrahom je vždy záhradník a majiteľom artefaktu kráľovský hvezdár. Belgarat sa teda urýchlene vybral do najvyššej veže na hrade.
Hneď ako otvoril dvere, do nosa mu vrazil prenikavý zápach čpavku a síry. Hvezdár na to: "Dnes už hvezdárstvo nič nevynáša, musel som začať s alchýmiou." Belgarat pri zvuku toho chrapľavého hlasu vyskočil a o chvíľu, keď uvidel, komu hlas patrí, takmer spadol z nôh. Hvezdárova postava bola celá pokrútená, tu noha, tam ruka a namiesto jedného oka mu žiaril obrovský drahokam. Tu Belgarat videl, že konečne našiel to, čo hľadal, posvätný Aldurov orb. "Ó, veľký hvezdár, múdrosť prebýva na tvojom čele a tvoje roky sú mnohé..." "No že no, tie rečičky si nechaj pre iných, vidím na tebe, že si mi prišiel zobrať oko a pravdu povediac, už by mi to aj dobre padlo, ale nemôžem ho vybrať, kým sa nezbavím kliatby". Belgarat sa ochotne ponúkol, že on ten problém vyrieši. Hvezdár teda spustí: Vždy keď je spln, príde za mnou duch morského leva a žiada odpoveď na svoju otázku. Zakaždým vyberie niekoľko hviezd a on, lev, chce vedieť, ako ďaľeko je od nás k-ta z nich. Ja som však už starý hvezdár a viem porovnať naraz len dve hviezdy a navyše kvôli tomu oku ani neviem, ktorá je bližšie, viem len povedať vzdialenosť bližšej z nich. Navyše odpoveď chce počuť hneď, inak mi pričaruje nový prst. Už teraz ich mám 47. Tu si Belgarat vzdychol a nakoľko si s touto úlohou nevedel dať rady, otvoril mocný portál do nášho sveta a obracia sa na vás.
Predpokladajte, že máte v poli pre každú dvojicu rôznych hviezd uloženú vzdialenosť bližšej z nich od nás. Navyše môžete predpokladať, že žiadne dve hviezdy nemajú od nás tú istú vzdialenosť. Na vstupe máte zadané číslo k. Vypíšte vzdialenosť k-tej hviezdy (hviezdy sú číslované od 1 do N) alebo správu, že sa zo známych údajov určiť nedá.
Pole:
-- 31 9 31 31 -- 9 32 9 9 -- 9 31 32 9 --k=1
31
(V tomto prípade vieme určiť, že prvá hviezda je vo vzdialenosti 31 a tretia vo vzdialenosti 9. V skutočnosti druhá hviezda je vo vzdialenosti 50 a štvrtá vo vzdialenosti 32, to už ale z daných údajov určiť nevieme.)
(15 bodov)
V hlbokom vesmíre v galaxii zvanej Húsenková dráha má svoje mesto planéta, ktorá sa volá Teleportka. Možno už tušíte, že toto meno nedostala náhodou. Obyvatelia tejto planéty sa totiž vedia premiestňovať z jedného miesta na druhé najrýchlejšou cestou (aspoň my pozemšťania si to myslíme), teda pomocou teleportu. Ale nemyslite si, že to majú úplne super vymakané! Kto chce používať na premiestňovanie teleport, musí úspešne absolvovať kurz teleportingu, a kto na to nemá, musí chodiť po svojich. Na kurze sa naučia, ako obsluhovať teleport a ako to celé funguje.
V každom meste Teleportky je určitý počet teleportovacích miest, nazývaných odpichový teleport. Má tvar kruhu a v strede sa nachádza riadiaci pult, pomocou ktorého sa teleporťania premiestňujú. Postavia sa na kruh a stlačia tlačítko označujúce cieľ, kam sa chcú dostať a za sekundu sa nachádzajú už v mieste určenia. (Bohužiaľ, nemôžu sa z každého odpichového teleportu dostať všade, a to áe sa dá z mesta A teleportovať do mesta B,neznamená, že sa musí dať aj z B do A).
Keďže teleporťania, mohli takýmto spôsobom precestovat za deň aj milión kilometrov, už si vôbec nelámali hlavu s tým, že ži vôbec chodia najkratšou cestou. Napríklad keď sa chceli dostat z mesta A do mesta E kľudne išli aj takto: z A do B potom do C, potom do D, potom do B, potom do C a nakoniec do E, a nikomu nevadilo, že existuje aj kratšia cesta. Teda skoro nikomu, jeden bezvýznamný filozof sa nad tým stále zamýšlal. Dlho, dlho nič nevymyslel, ale zrazu ho napadlo, že on ani nevie, koľko vlastne takých ciest je...
Na vstupe je číslo K, počet miest( číslo N ) a potom zoznam dvojíc, určujúci medzi ktorými mestami sa dá priamo teleportovať(dvojica (a, b) určuje že sa dá z a do b ). Napíšte program ktorý vypočíta, koľko je všektých možných sledov (sled je definovaný ako postupnosť miest a0,a1, ... , ak-1,ak,a pre všetky i od 0 do k-1 ,sa dá priamo teleportovať z mesta ai do ai+1, a dížka sledu je k) teleportovania dĺžky práve K.
N=3, K=1234457542
0 1
1 2
2 0
65536
(15 bodov)
Malý Lukáš dostal na Vianoce M rovnakých kociek, s ktorými sa teraz celé dni hrá. Už z nich postavil postavil všetko od katedrály po električku a pomaly ho to začalo nudiť. V tom ho však napadlo stavať z kociek mrakodrapy a nie hocikoľko, ale práve N. Každý mrakodrap sa skladá z jedného stĺpca kociek a výšky mrakodrapov naviac tvoria zľava doprava neklesajúcu postupnosť.
Toto ho tiež začalo po chvíli nudiť a tak si to sťažil. Uvedomil si, že dve rozostavenia mrakodrapov sa dajú lexikograficky porovnať. Ak a1,..., a_n a b1,..., bn sú dve rozostavenia, tak prvé je menšie ako druhé práve vtedy, keď sa na prvých i-1 pozíciach zhodujú a platí ai < bi. Lukáš by si rád postavil k-te rozostavenie mrakodrapov, lenže je ešte príliš malý na takúto matematiku.
Na vstupe sú tri čísla M, N, K. Úlohou je nájsť K-te rozostavenie N mrakodrapov, ktoré sú poskladané práve z M kociek.
M=9, N=4, K=5
1 2 3 3
(15 bodov)
Časť 47-rozmerného hyperpriestoru sa bude rozpredávať na hyperparcely. Dotyčná časť hyperpriestoru má tvar 17-rozmerného hyperkvádra, ktorého hrany sú rovnobežné so súradnicovými osami a až q. "Ľavý dolný" roh tohto hyperkvádra má súradnice (0,0,...,0), "pravý horný" roh má súradnice (10,10,...,10). (Ak si neviete predstaviť hyperkváder, predstavte si 17-rozmerné pole, ktorého každý rozmer má veľkosť 10.)
Hyperpozemkový úrad pripravil návrh rozdelenia tohto hyperkvádra na hyperparcely. Ale keďže v 17 rozmeroch sa ani hyperdivá srnka nevyzná, je dosť možné, že sú v návrhu chyby. Potrebovali by vašu pomoc.
Na vstupe je popis jednotlivých hyperparciel. Každá hyperparcela je zadaná sústavou podmienok. Podmienka má tvar x?c, kde x je súradnicová os, ? je znamienko (=, <, >, <= alebo >=) a c je celé číslo od 0 do 10.
Váš program by mal postupne overiť:
1: "a>3 a>2", 2: "a<=3 b>5", 3: "b<6 a<=3"
OK
1: "a=0 a=1", 2: "a>=2"
Hyperparcela 1 je prázdna.
1: "a>=5", 2: "q<=6"
Hyperparcely 1 a 2 sa prekrývajú.
1: "a>=5", 2: "a<=4 b>7", 3: "a=4 c>=14 b=7",
4: "a<5 b<7", 5: "c<13 a=4 b=7", 6: "a<4 b=7"
Nekompletné pokrytie.
(tak okolo 20 bodov)
Na úvod sa stručne zoznámime s binárnou operáciou xor (exclusive or, po našom "buď alebo"). Budeme ju zapisovať ⊻ (malo by byť plus v krúžku). Pre hodnoty 0 (false, nepravda) a 1 (true, pravda) ju definujeme nasledovne:
0 ⊻ 0 = 1 ⊻ 1 = 0, 0 ⊻ 1 = 1 ⊻ 0 = 1
Teda x ⊻ y=1 práve vtedy, ak práve jedna z premenných x, y je 1.
Teraz môžme operáciu xor definovať aj pre ľubovoľné dve nezáporné celé čísla x, y nasledovne: Zapíšeme pod seba ich zápisy v dvojkovej sústave, kratší prípadne doplníme zľava nulami. Nech i-te cifry x, y sú xi a yi. Potom i-ta cifra výsledku je (xi ⊻ yi). Príklad:
17 ⊻ 9 = (10001)2 ⊻ (01001)2 = (11000)2 = 24
Na operáciu xor sa môžeme dívať ako na sčítanie v dvojkovej sústave, pri ktorom zabúdame robiť prenos od nižších rádov k vyšším. Všimnite si, že táto operácia je komutatívna, asociatívna a platí x ⊻ x=0.
Pokračovať budeme rozprávaním o pirátskej truhlici. Profesor Quilenius na jednej zo svojich početných výprav zablúdil do Karibiku. Ako áno, ako nie, po dlhom a finančne vyčerpávajúcom hľadaní objavil jednu truhlicu plnú zlatých dublónov. Lenže čo s ňou v ďalekej cudzine? Ideálne by bolo doviezť ju domov a tam ju spokojne predať... ehm, chcem povedať darovať múzeu. Lenže na letenku domov mu už nezostávalo peňazí.
Spomenul si ale na svojho priateľa profesora Jonesa, toho času sa nachádzajúceho v Anglicku. Keby mu truhlicu poslal, profesor Jones by sa o ňu určite dobre postaral a dostal by jeho, Quilenia, späť domov. Ale keď mu truhlicu len tak pošle, skoro určite ju po ceste vykradnú! A naopak, ak ju poriadne zamkne, ani Jones ju neotvorí... Čo s tým?
Netrvalo dlho a v hlave profesora Quilenia sa zrodil plán -- diabolsky rafinovaný, a pritom tak jednoduchý. Nasledoval telefonát s profesorom Jonesom, všetko si dohodli a tak aj spravili. O dva týždne už bol obsah truhlice v rukách profesora Jonesa a profesor Quilenius na ceste domov. Pýtate sa, ako to spravili? Jednoducho:
Keď si tento príbeh prečítali Alica s Bobom, zdalo sa im, že je to ideálne riešenie ich problému -- ako si posielať správy bez toho, aby si ich mohla poštárka čítať. Vymysleli si nasledujúci postup:
Cyril a Diana mali podobný problém. Cyril však prišiel na jednoduché riešenie. Keď sa raz s Dianou stretli, dohodli si kľúč K. Bezpečný prenos správy je teraz omnoho jednoduchší:
A: 81 d5 62 63 83 4a 34 57 66 66 07 3d 78 39 39 96 9c 38 31 B: 80 e0 ac bc 12 7e 94 32 21 02 26 7f 1c 9a 03 96 9d 22 1c A: 52 41 bc bc b1 44 d2 16 33 44 52 29 16 d9 1a 6b 73 71 0cZistite obsah správy.
C1: 17 6f c8 3c 06 6f 39 8c 37 37 c9 37 c0 ce d8 db 2f 85 2e 63 c6 e2 62 f9 43 4c 73 08 4a 4d 75 af 2c b0 c8 cc 80 4b 5f 05 57 25 73 84 C2: 17 65 d4 39 4a 77 22 88 33 37 c5 33 d0 da cf d9 29 97 67 71 83 a4 64 f7 17 4c 37 09 4f 47 21 b6 6d ad c4 d3 cf 44 47 1f 4f 3e 77 8bZistite čo najpresnejšie ich obsahy. Môže sa vám hodiť nejaký zoznam slovenských slov.