KSP
- Home
- Novinky
- Pravidlá
- FAQ
- Kuchárka
- Liaheň
Séria
Akcie
Ostatné
Iné semináre
- Trojsten
- KMS
- FKS
- Iné súťaže

Korešpondenčný seminár z programovania

Príklady 1. kola letnej časti 22. ročníka KSP

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!

„.... .. ......, .... .. ......" (nehodiace/hodiace sa nedoplňte/doplňte)
KSPáci

O hvezdárovi bez oka
Ortonormálny teleport
Obrovské mrakodrapy
Opäť v 47. hyperpriestorovej dimenzii
Opatrne s XORovaním!

1. O hvezdárovi bez oka

(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.

Úloha

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á.

Príklad

Vstup

Pole:

-- 31  9 31
31 --  9 32
 9  9 --  9
31 32  9 --

k=1

Výstup

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.)

2. Ortonormálny teleport

(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...

Úloha

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 a₀,a₁, ... , a_k-1,a_k,a pre všetky i od 0 do k-1 ,sa dá priamo teleportovať z mesta a_i do a_i+1, a dížka sledu je k) teleportovania dĺžky práve K.

Príklad

Vstup

N=3, K=1234457542
0 1
1 2
2 0

Výstup

65536

3. Obrovské mrakodrapy

(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 a₁,..., a_n a b₁,..., b_n 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í a_i < b_i. Lukáš by si rád postavil k-te rozostavenie mrakodrapov, lenže je ešte príliš malý na takúto matematiku.

Úloha

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.

Príklad

Vstup

M=9, N=4, K=5

Výstup

1 2 3 3

4. Opäť v 47. hyperpriestorovej dimenzii

(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.

Úloha

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ť:

či má každá hyperparcela nenulový hyperobjem
ak áno, či sa žiadne dve hyperparcely neprekrývajú
ak nie, či hyperparcely dokopy pokrývajú celý hyperkváder

Príklad

Vstup #1

1: "a>3 a>2", 2: "a<=3 b>5", 3: "b<6 a<=3"

Výstup #1

Vstup #2

1: "a=0 a=1", 2: "a>=2"

Výstup #2

Hyperparcela 1 je prázdna.

Vstup #3

1: "a>=5", 2: "q<=6"

Výstup #3

Hyperparcely 1 a 2 sa prekrývajú.

Vstup #4

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"

Výstup #4

Nekompletné pokrytie.

5. Opatrne s XORovaním!

(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ú x_i a y_i. Potom i-ta cifra výsledku je (x_i ⊻ y_i). Príklad:

17 ⊻ 9 = (10001)₂ ⊻ (01001)₂ = (11000)₂ = 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:

Profesor Q. dal na truhlicu pevný zámok a poslal ju profesorovi J.
Profesor J. truhlicu nevie otvoriť, ale zato na ňu vie pridať druhý, rovnako pevný zámok. Potom pošle truhlicu späť.
Profesor Q. otvorí svoj zámok. Truhlica stále ostáva zamknutá zámkom profesora J. Pošle truhlicu späť.
Profesor J. otvorí svoj zámok a má otvorenú truhlicu.

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:

Alica zoberie správu M, ktorú chce poslať. Zapíše ju ako postupnosť bitov ASCII hodnôt znakov správy. Zvolí si kľúč K_A -- náhodnú postupnosť bitov rovnakej dĺžky ako zápis M. Správu M prexoruje kľúčom K_A a pošle ju Bobovi.
Bobovi prišla správa. Zvolí si rovnako dlhý kľúč K_B, prexoruje ním ju a pošle ju späť.
Alici prišla správa, prexoruje ju K_A a pošle ju späť.
Bobovi prišla správa, prexoruje ju K_B a prečíta si výsledok.

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ší:

Cyril zoberie správu M, ktorú chce poslať. Zapíše ju ako postupnosť bitov ASCII hodnôt znakov správy. Zoberie začiatok kľúča K rovnakej dĺžky a prexoruje ju ním. Výslednú správu S pošle Diane.
Diane prišla správa. Zoberie začiatok kľúča K rovnakej dĺžky a prexoruje ju ním. Výsledok si prečíta.

Cyril ubezpečil Dianu, že tento spôsob je úplne bezpečný -- poštárka vidí len S a o M nezistí nič okrem dĺžky.

Úloha

Rozcvička 1: Ukážte, že výsledok, ktorý Bob dostane, je naozaj Alicina správa.
Rozcvička 2: Ukážte, že Cyril má pravdu. Ak poštárka pozná S, tak ku každej správe M' rovnakej dĺžky ako S existuje práve jeden kľúč K', ktorý by zašifroval M' na S.
Analógie nie vždy fungujú. Napríklad postup Alice a Boba nie je taký skvelý, ako sa zdá. Poštárka odpočula nasledujúcu komunikáciu medzi Alicou a Bobom:
```
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 0c
```
Zistite obsah správy.
Ani nápad profesora Quilenia nebol dokonalý. Predpokladajme, že profesor Smith vie o truhlici a chce sa zmocniť jej obsahu. Navrhnite, čo má spraviť, aby sa mu to podarilo.

Aj Cyrilov postup má svoje slabiny. Kľúč K by totiž mali použiť len raz. Prečo? Cyril s Dianou použili dvakrát ten istý kľúč K. Poštárka zachytila obe správy:

C₁: 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
C₂: 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 8b

Zistite čo najpresnejšie ich obsahy. Môže sa vám hodiť nejaký zoznam slovenských slov.

Podporte nás

Účet

Prihlasovanie už nefunguje. Používaj nový KSP web.

kontakt