Zadanie
Ak máte akékoľvek otázky ohľadom tejto úlohy napíšte Edovi “Baklažánovi” Batmendijnovi na
Janko a Marienka sú väzňami v perníkovej chalúpke a radi by ušli. Marienka už aj vymyslela plán. Ježibaba totiž každý deň chodí spolu s Marienkou do lesa zbierať čarovné bylinky. V tom čase by Janko mohol ujsť a kým by sa Ježibaba s Marienkou vrátili, stihol by už byť dostatočne ďaleko a zavolať nejakú pomoc pre Marienku.
Celý plán však má jeden háčik. Marienka sa totiž s Jankom môže dohadovať iba večer (keď upratuje okolo chlievika) a Ježibaba sa až ráno rozhodne, kedy pôjde na bylinky (vtedy sa to dozvie aj Marienka). Ak by sa Janko pokúsil o útek, keď je Ježibaba v chalúpke, zle-nedobre by sa mu povodilo a Ježibaba by sprísnila opatrenia. Preto musí Marienka čas Ježibabinho odchodu do lesa Jankovi zakódovať do toho, ako mu naservíruje raňajky.
Úloha
Janko máva každý deň na raňajky niekoľko koláčov, z ktorých každý je buď makovník, alebo orechovník. Marienka mu ich vždy v kuchyni poukladá do jedného radu na podlhovastý podnos, pričom sa sama rozhodne, na ktorých pozíciách v rade budú makovníky a na ktorých orechovníky (Ježibaba má vždy v zásobe napečenú hŕbu makovníkov aj orechovníkov, takže ak by Marienka chcela, mohla by Jankovi naservírovať samé makovníky, alebo samé orechovníky). Následne Ježibaba podnos odnesie Jankovi. Keďže z jedného konca Ježibabinho podnosu je kúsok odštiepený, vie Janko jednoznačne určiť na ktorej strane je začiatok radu koláčov a na ktorej strane je jeho koniec.
(2 body) Janko máva na raňajky vždy 5 koláčov. Ježibaba chodieva na bylinky niekedy medzi 11:00 a 14:50. Marienka by Jankovi chcela zakódovať čas Ježibabinho odchodu s presnosťou na desať minút, teda chce vedieť zakódovať ľubovoľný z časov 11:00, 11:10, 11:20, …, 14:50 (spolu 24 možností). Navrhnite spôsob, ako to urobiť. Presnejšie, navrhnite dve veci:
- Postup, podľa ktorého sa Marienka na základe času Ježibabinho odchodu rozhodne, ktoré z koláčov majú byť makovníky a ktoré orechovníky.
- Postup, podľa ktorého Janko na základe donesených koláčov zistí, v ktorom čase Ježibaba odíde.
Nezabudnite, že Janko s Marienkou sa môžu večer na spôsobe kódovania dohodnúť, od rána sa však už rozprávať nemôžu.
(2 body) Janko máva na raňajky 8 koláčov. S akou veľkou presnosťou mu Marienka vie zakódovať čas Ježibabinho odchodu? Presnejšie povedané, koľko rôznych možností môže do ôsmich koláčov zakódovať? Svoju odpoveď zdôvodnite!
(1 bod) Ježibaba odchádza do lesa vždy medzi 10:00 a 16:59. Keďže každá minúta je drahá, Marienka by chcela čas jej odchodu zakódovať s presnosťou na minútu (chce teda vedieť rozlíšiť 420 rôznych možností). Koľko najmenej koláčov by Janko musel mať na raňajky, aby sa jej to mohlo podariť? Svoju odpoveď zdôvodnite!
(5 bodov) Ježibaba si vypestovala jeden veľmi nepríjemný zvyk: keď ide podnos s koláčmi odniesť Jankovi, najprv jeden z koláčov zje. Potom sa zapýri a na miesto zjedeného koláča doplní nejaký koláč zo zásoby – možno rovnakého druhu ako ten zjedený a možno opačného. Marienka chce Jankovi vedieť zakódovať 240 rôznych možností (časy medzi 11:00 a 14:59 s presnosťou na minútu) tak, aby:
- V prípade, že Ježibaba zjedený koláč nahradila rovnakým, Janko normálne zistil, kedy Ježibaba odíde a ušiel v správnom momente.
- V prípade, že Ježibaba zjedený koláč nahradila opačným, Janko zistil, že sa niečo pokazilo a útek radšej odložil na nasledujúci deň.
Opäť teda treba navrhnúť dva postupy, prvý pre Marienku, podľa ktorého na základe času Ježibabinho odchodu poukladá na podnos koláče a druhý pre Janka, podľa ktorého na základe koláčov na podnose buď zistí čas Ježibabinho odchodu, alebo aspoň zistí, že Ježibaba niektorý koláč vymenila za koláč opačného druhu. Váš spôsob kódovania musí fungovať vo všetkých prípadoch, bez ohľadu na to, ktorý koláč Ježibaba vymení.
Počet koláčov, ktoré Janko dostane na raňajky, si tento raz môže určiť Marienka. Tento počet však musí Ježibabe oznámiť ešte večer, nemôže sa teda o počte koláčov rozhodnúť až na základe času Ježibabinho odchodu. Snažte sa vymyslieť riešenie používajúce čo najmenej koláčov. Za ľubovoľné funkčné riešenie tejto podúlohy môžete získať až 3 body. Plných 5 bodov môžete dostať, ak bude vaše riešenie využívať iba 9 koláčov (áno, dá sa to :)).
(5 bodov) Ježibaba má rovnaký nepríjemný zvyk ako v podúlohe d), tentoraz však Janko s Marienkou navyše vedia, že sa chystá Janka upiecť už pozajtra ráno a teda si nemôžu dovoliť čakať ešte jeden deň. Preto sa musia dohodnúť na takom spôsobe kódovania, aby Janko vedel zistiť čas Ježibabinho odchodu, aj keby ktorýkoľvek koláč zjedla a nahradila koláčom opačného druhu. Čas Ježibabinho odchodu chcú tentoraz vedieť kódovať s presnosťou na sekundu (každá sekunda predsa môže byť rozhodujúca!), pričom Ježibaba môže ísť do lesa kedykoľvek medzi 9:00:00 a 20:59:59, musia teda vedieť rozlíšiť \(43\,200\) rôznych možností.
Podobne ako v podúlohe d), aj v tejto podúlohe si môžete počet koláčov zvoliť sami, pričom opäť je cieľom použiť čo najmenej koláčov. Vaše riešenie však musí fungovať vždy, bez ohľadu na to, ktorý koláč Ježibaba vymení. Za akékoľvek funkčné riešenie môžete dostať až 3 body. Plných 5 bodov môžete dostať, ak vaše riešenie nepoužíva viac ako 34 koláčov.
(3 bonusové body) Bonusové body môžete získať, ak vyriešite podúlohu e) iba s pomocou 25 koláčov, ktoré však tentoraz Marienka nebude servírovať v jednom dlhom rade, ale v štvorci \(5 \times 5\) na štvorcovom podnose (ktorý má v jednom rohu kúsok odbitý, takže Janko vie povedať, kde je ľavý horný roh :)).
Podúlohy a, b, c
Počet možností
Zásadnou otázkou pre prvé tri podúlohy tejto úlohy je “Koľko možností vieme rozlíšiť pomocou \(X\) koláčov?”. Inými slovami, koľkými rôznymi spôsobmi vie Marienka naukladať koláče na podnos, ak ich má použiť presne \(X\)?
Ak má Marienka poslať Jankovi iba jeden koláč, má dve možnosti: buď mu pošle makovník, alebo orechovník. Ak má poslať dva koláče, má dve možnosti, akého druhu bude prvý koláč, a v oboch prípadoch sa ešte môže rozhodnúť, akého druhu bude druhý koláč. Spolu má teda \(2 \cdot 2 = 4\) možnosti, ako vybrať koláče: MM, MO, OM, OO (kde M reprezentuje makovník a O orechovník). Ak má Marienka poslať tri koláče, typy prvých dvoch vie určiť štyroma rôznymi spôsobmi (ktoré sú rovnaké, ako keď posielala iba 2 koláče) a pre každý z týchto spôsobov má dve možnosti, čo dať na koniec. Spolu teda má \(4 \cdot 2 = 8\) možností (sú to MMM, MMO, MOM, MOO, OMM, OMO, OOM, OOO). A takto to bude pokračovať ďalej: ak má Marienka poslať 4 koláče, bude mať dvakrát viac možností, než keď mala poslať 3, ak má poslať 5, bude mať dvakrát viac možností než pri štyroch atď.. Všeobecne, pomocou \(X\) koláčov vie Marienka rozlíšiť \(2^X\) možností.
To znamená, že pomocou \(8\) koláčov vie Marienka rozlíšiť \(2^8 = 256\) rôznych časov (čo je odpoveď na podúlohu b.). V podúlohe c. potrebujeme rozlíšiť 420 rôznych možností. 8 koláčov nám na to nestačí, 9 koláčov nám dáva \(2^9 = 512\) rôznych možností, čo nám už stačí. Na zakódovanie 420 rôznych možností teda potrebujeme minimálne 9 koláčov.
Ako kódovať
Druhou otázkou je, ako do koláčov zakódovať informáciu o čase. Veľmi jednoduchý prístup, ktorý by bol ale pre Janka a Marienku pomerne pracný, je vypísať si do tabuľky všetky časy, ktoré chceme zakódovať a ku každému z nich priradiť nejakú inú možnosť servírovania koláčov. Tabuľka pre podúlohu a) by teda mohla vyzerať napríklad takto:
| čas | koláče | čas | koláče | čas | koláče | ||
|---|---|---|---|---|---|---|---|
| 11:00 | MMMMM | 12:20 | MOMMM | 13:40 | OMMMM | ||
| 11:10 | MMMMO | 12:30 | MOMMO | 13:50 | OMMMO | ||
| 11:20 | MMMOM | 12:40 | MOMOM | 14:00 | OMMOM | ||
| 11:30 | MMMOO | 12:50 | MOMOO | 14:10 | OMMOO | ||
| 11:40 | MMOMM | 13:00 | MOOMM | 14:20 | OMOMM | ||
| 11:50 | MMOMO | 13:10 | MOOMO | 14:30 | OMOMO | ||
| 12:00 | MMOOM | 13:20 | MOOOM | 14:40 | OMOOM | ||
| 12:10 | MMOOO | 13:30 | MOOOO | 14:50 | OMOOO |
Na takejto tabuľke sa Janko s Marienkou dohodnú večer a obaja si ju niekam napíšu (alebo sa ju naučia naspamäť). Keď chce ráno Marienka poslať Jankovi čas Ježibabinho odchodu, nájde v tabuľke riadok s týmto časom a príslušným spôsobom poukladá koláče na podnos. Keď Janko dostane koláče, nájde v tabuľke riadok s takto naukladanými koláčmi a pozrie sa, akému času koláče zodpovedajú.
Tento prístup funguje vždy a je fajn, ak je tabuľka dostatočne malá. Existujú však aj spôsoby, kde si netreba pamätať tabuľku. Jeden z nich je nasledovný:
Všetky časy si očíslujeme zaradom číslami od 0 po počet časov - 1 (v podúlohe c. by teda číslo \(i\) dostal čas \(i\) minút po 10:00). Čas číslo \(i\) potom Marienka zakóduje tak, že si najprv číslo \(i\) napíše v binárnej sústave1. Ak malo číslo menej cifier, než je predpísaný počet koláčov, pripíše k číslu zľava toľko núl, aby výsledná postupnosť mala dostatočný počet cifier. Túto postupnosť potom Marienka naukladá na podnos, pričom nulu bude reprezentovať makovníkom a jednotku orechovníkom. Keď Janko dostane koláče, prečíta makovníky ako nuly a orechovníky ako jednotky a takto získané binárne číslo prevedie naspäť do desiatkovej sústavy2. Tým získa číslo času, kedy má ujsť.
Všimnite si, že aj tabuľka uvedená ako riešenie podúlohy a. bola v skutočnosti vytvorená týmto spôsobom.
Podúloha d
Ak by Ježibaba s koláčmi nerobila nič, na rozlíšenie 240 možností by sme potrebovali 8 koláčov. Jednoduchý spôsob, ako vyriešiť túto podúlohu pomocou 16 koláčov je poslať Jankovi zakódovaný čas dvakrát. Teda do prvých 8 koláčov Marienka zakóduje požadovaný čas a druhých 8 koláčov bude rovnakých ako prvých 8. Ak Ježibaba niektorý z koláčov vymení za koláč opačného druhu, nebude sa prvá osmica koláčov zhodovať s druhou a podľa toho Janko zistí, že sa niečo stalo. Ak sa prvá a druhá osmica budú zhodovať, Janko bude vedieť, že všetko je v poriadku a z prvej osmice dekóduje čas úteku.
Ako sme spomínali v zadaní, existuje aj riešenie využívajúce iba 9 koláčov. To funguje nasledovne: Marienka do prvých 8 koláčov zakóduje čas a na deviate miesto dá taký koláč, aby bol počet orechovníkov na podnose párny. Ak Ježibaba niektorý koláč vymení za koláč iného druhu, tak buď zmenila makovník za orechovník (čím počet orechovníkov stúpol o 1), alebo orechovník za makovník (čím počet orechovníkov klesol o 1). V každom prípade, po takejto výmene by bol počet orechovníkov nepárny. Keď teda Jankovi prídu koláče, najprv spočíta všetky orechovníky a zistí, či ich je párny počet. Ak áno, tak je všetko v poriadku a z prvých 8 koláčov môže dekódovať čas. Ak nie, potom musela Ježibaba niečo zmeniť.
Podúloha e
Na rozlíšenie 43 200 možností bude Marienka potrebovať aspoň 16 koláčov. Jednoduchým riešením je poslať zakódovaný čas trikrát (použijeme teda \(3 \cdot 16 = 48\) koláčov). Ak Ježibaba nejaký koláč zmení, pokazí tým iba jednu z troch kópií Marienkinho kódu, aspoň dve kópie budú stále neporušené. Janko sa teda pozrie na jednotlivé šestnástice koláčov a buď sú všetky tri rovnaké (vtedy z nich jednoducho dekóduje čas), alebo sú dve rovnaké a jedna iná – vtedy vie, že tá jedna iná je zmenená a čas dekóduje zo zvyšných dvoch.
Iné, prefíkanejšie riešenie využíva trik, ktorý sme urobili v podúlohe d.: na to, aby sme vedeli zistiť, že Ježibaba niečo zmenila, nám stačí jeden koláč navyše. Do 16 koláčov teda Marienka zakóduje čas a sedemnásty koláč vyberie tak, aby bol počet orechovníkov párny. Následne týchto 17 koláčov ešte raz zopakuje (dokopy teda použije 34 koláčov). Keď Janko dostane koláče, pozrie sa, či sa prvá polovica kolačov zhoduje s druhou. Ak áno, potom vie, že Ježibaba nezmenila druh žiadneho koláča a normálne dekóduje čas. Ak sa sedemnástice nezhodujú, Janko vie povedať, ktorá z nich bola zmenená: je to tá, ktorá obsahuje nepárny počet orechovníkov. Z tej druhej teda môže dekódovať čas.
Podúloha f
To najlepšie nakoniec: riešenie s 25 koláčmi. Ako bolo povedané v zadaní, koláče si tentoraz usporiadame do štvorca \(5 \times 5\). Do 16 koláčov tvoriacich štvorec \(4 \times 4\) v ľavom hornom rohu nášho štvorca \(5 \times 5\) Marienka zakóduje čas úteku. V prvých štyroch riadkoch doplní piaty koláč tak, aby v každom z týchto riadkov bol párny počet orechovníkov. Nakoniec doplní koláčmi posledný riadok tak, aby bolo v každom stĺpci párne veľa orechovníkov.
V každom stĺpci aj v každom z prvých štyroch riadkov je teda párny počet orechovníkov. Koľko orechovníkov je v piatom riadku? Keďže v každom stĺpci je párne veľa orechovníkov, aj v celom štvorci bude párne veľa orechovníkov. V prvých štyroch riadkoch je dohromady tiež párny počet orechovníkov (lebo v každom z nich je párny počet), teda aj v piatom riadku ich musí byť párny počet.
Ak Ježibaba vymení nejaký koláč za koláč opačného druhu, v riadku obsahujúcom tento koláč sa počet orechovníkov zmení na nepárny. Rovnako aj v stĺpci obsahujúcom tento koláč. Keď teda Janko dostane koláče, najprv si spočíta, či je v každom riadku párny počet orechovníkov. Ak áno, potom Ježibaba žiaden koláč nevymenila za opačný a Janko môže dekódovať čas. Druhá možnosť je, že v jednom riadku je počet orechovníkov nepárny. Vtedy Janko vie, že Ježibaba zmenila niektorý z koláčov v tomto riadku. Spočíta počty koláčov v jednotlivých stĺpcoch a podľa toho, v ktorom stĺpci je nepárny počet orechovníkov vie, ktorý koláč Ježibaba vymenila. Predstaví si, že by na jeho mieste bol koláč opačného druhu (teda taký koláč, aký tam dala Marienka) a dekóduje čas úteku.
http://www.gym-informatika.estranky.cz/clanky/dvojkova-sustava.html↩
Tento krok môže vynechať, ak je dostatočný macher na to, aby všetko rátal v binánej sústave.↩
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.