Zadanie
Keď sa Syseľ s Majkou vracali domov z Ameriky, museli absolvovať niekoľkohodinový prestup v Amsterdame. No a aby len tak bezcieľne nesedeli na letisku, rozhodli sa tento čas využiť na prechádzku po okolí.
Okrem mnohých obchodov špecifických pre tento kraj sa zastavili aj v obchode so starožitnosťami. Kým sa Majka nadchýnala keramikou, Syseľ našiel niečo zaujímavejšie – malú čiernu skrinku s ciferníkom. Nastavil na nej číslo 27 a natiahol ju kľúčikom uprostred. Skrinka chvíľku hrkotala a potom sa čísla na ciferníku prestavili na 55. Syseľ skúsil 42 a dostal 85. Celý nadšený z toho, čo našiel, išiel za Majkou. Predavač si všimol jeho nadšenie pre skrinku a dal mu zaujímavú ponuku. Ak príde na to, ako skrinka funguje a donúti ju zobraziť číslo 47, tak si ju môže nechať. Vraj o ňu aj tak nik iný nemá záujem.
Syseľ s Majkou samozrejme zistili ako skrinka funguje a odniesli si ju domov. Dokonca našli na skrinke prepínač, ktorý mení jej funkciu. Majú teda kopu zaujímavých hlavolamov, o ktoré sa s vami chcú podeliť.
Úloha
Dostanete prístup k simulátoru čiernej skrinky. Vždy, keď do nej vložíte nejaké číslo, skrinka niečo vypíše (číslo, slovo…) podľa jednoduchého pravidla.
Vašou úlohou bude toto pravidlo odhaliť a nájsť vstupné číslo také, aby skrinka vypísala požadovanú vec.
Hra má 10 úrovní, za každú získate bod. Náročnosť stúpa spolu s úrovňami, môžete ich však riešiť v ľubovoľnom poradí.
Odovzdávanie a bodovanie
Za každú vyriešnú úroveň dostanete jeden bod. K tejto úlohe netreba odovzdávať žiadny popis ani program. Simulátor, spolu so všetkými potrebnými informáciami o odovzdávaní nájdete na stránke http://ksp.sk/hry/32/1/1.
Level 1
Po pár pokusoch si bolo možné všimnúť, že k vstupnému číslu sa vždy pripočítalo číslo \(1\). Na dosiahnutie čísla \(47\) teda stačilo zadať \(46\).
Level 2
Tu sa zobralo vstupné číslo a prevrátilo sa v ňom poradie cifier. Číslo \(123\) získame pomocou \(321\).
Level 3
Tento level počítal ciferný súčet vstupu. Keďže \(42 = 6 \cdot 7\), mohli ste napríklad zadať \(777777\).
Level 4
Fakt, že máte dosiahnuť \(OK\), mohol byť mierne odstrašujúci. V skutočnosti vám však skrinka odpovedala, či má byť číslo väčšie, alebo menšie.
Pre človeka bolo najjednoduchšie najskôr nájsť správnu dĺžku výsledného čísla a potom postupne hľadať jednotlivé cifry. Výsledok nebol zvolený úplne náhodne. Bolo to prvých \(8\) desatinných miest čísla \(\pi\): \(14159265\).
Ak by sme však chceli minimalizovať počet pokusov, mohli by sme skúsiť ešte efektívnejší postup. Najskôr nájdeme prvé minimum a maximum. Minimum môže byť napríklad nula a maximum prvé číslo, ktoré nám už bude vypisovať odpoveď menšie. Tieto nám určia nejaký interval, v ktorom sa hľadané číslo môže nachádzať. Spýtame sa presne na stred tohto intervalu. Nech nám krabička odpovie akokoľvek, práve sme zmenšili interval možných odpovedí na polovicu (ak sme, náhodou, číslo neuhádli). Opakovaním tohto postupu sa rýchlo dopracujeme k výsledku. V informatike sa táto metóda nazýva binárne vyhľadávanie.
Level 5
Prvá vec, ktorú ste si mohli všimnúť, je, že skrinka zachováva počet cifier. Prvú cifru nikdy nemení. Druhú vždy zvýši o \(1\), tretiu zvýši o \(2\), atď. Ale ak je napríklad druhá cifra \(9\), tak z nej spraví \(0\), takže číslice sa cyklicky točia. Stačilo preto \(25252525\) cyklicky posunúť späť, čím získame \(24028068\).
Level 6
Predstavte si, že zoberiete všetkých \(26\) písmen anglickej abecedy a poskladáte z nich všetky možné slová. Tieto slová potom zoradíte. Najskôr podľa dĺžky a potom podľa abecedy. Takto získate postupnosť, ktorej prvky vám vracala šiesta krabička.
Na začiatku je prázdne slovo dĺžky \(0\). Nasleduje \(26\) samostatných písmen dĺžky 1. Potom sú všetky dvojice zoradené abecedne, atď. Niečo podobné využívajú tabuľkové procesory (napr. Microsoft Excel alebo LibreOffice Calc) na označenie stĺpcov.
Jeden spôsob, ako nájsť medzi týmito slovami \(PAPAGAJ\)-a, je postupovať podobne ako v leveli 4. Vieme totiž povedať, či slovo, ktoré sme dostali, je pred alebo za \(PAPAGAJ\)-om.
Druhá, rýchlejšia možnosť je toto číslo vypočítať. Najskôr musíme spočítať všetky menejpísmenkové slová. Prázdne slovo je jedno, jednopísmenkových je \(26\), dvojpísmenkových \(26 \cdot 26\) a \(n\)-písmenkových je \(26^n\). Spolu je to teda \(26^0 + 26^1 + 26^2 + \dots +26^6\) slov. Potom ešte musíme pripočítať všetky \(7\) písmenové slová, ktoré začínajú niečim pred \(P\) (\(15 \cdot 26^6\)), všetky slová začínajúce na \(PA\) ktoré majú tretie písmeno pred \(P\) (\(15 \cdot 26^4\)) a obdobné slová pre \(G\) a \(J\) (\(6 \cdot 26^2\) a \(9 \cdot 26^0\)). Po sčítaní dostaneme \(4961867752\) čo je počet slov pred slovom \(PAPAGAJ\) a teda aj jeho poradie.
Level 7
Nech napíšete takmer čokoľvek, výsledok je \(101010\). A máte nájsť \(POKLAD\)! Čo to má znamenať? Robia si z nás snáď srandu? Alebo že by \(101010\) niečo znamenalo? Nemôže to byť stopa na ceste k pokladu? Neskúsime ho zadať? BINGO! Získali sme ďalšiu stopu. Ak zadáme ju a postup zopakujeme ešte \(20\) krát, dostaneme sa k pokladu.
Wait! What? Má to aj nejaký hlbší zmysel? Samozrejme! Ak si totiž cestu k pokladu zaznačíte do mapy (na číselnú os), zistíte, že neskáče len tak náhodne, ale vždy skočí o polovicu toho, čo skákala predtým. A vždy zmení smer. Presnejšie povedané, v \(n\)-tom kroku skočí o \((-2)^{20-n}\) dopredu (kroky číslujeme od \(0\)). Znamená to, že musí skončiť približne v dvoch tretinách prvého skoku. Na domácu úlohu si rozmyslite prečo! Alebo si to aspoň nakreslite.
Level 8
Veľmi dobrý testovací vstup je napríklad \(8887777\). Vráti nám \(3847\). Čo to má znamenať? No presne to, čo ste napísali. Tri osmičky a štyri sedmičky. Takže \(123456\) nám vlastne hovorí, že správny vstup má byť jedna dvojka, tri štvorky a päť šestiek. Teda \(244466666\).
Level 9
Čas. Výborne. Dimenzia, ktorá nám chýbala. Vstup \(0\) vypíše aktuálny čas.
Nápad: Submitnúť o 4:13 ráno. Zamietnutý. (Či?)
Pozorovanie: číslo na vstupe vynásobené \(47\) je počet minút, ktorý sa k aktuálnemu času pripočíta.
Nápad: Nájsť najbližší čas pred 4:13, ku ktorému vieme pričítať nejaký jednoduchý násobok \(47\), a počkať tých najviac \(47\) minút. Zamietnutie závisí od jedinca1 a aktuálneho času.
Jedinec, ktorý predchádzajúci nápad zamietol, si mohol uvedomiť, že nie je špecifikovaný deň a teda sa vieme posunúť dopredu o viac ako \(24\) hodín. Takto sa vie k želanému času dostať bližšie a čakať menej. Alebo to môže vypočítať presne a potom zistiť, že sa medzičasom čas zmenil. Aj tak mu však patrí sláva.
Level 10
Konečne koniec. Čo si pre nás prichystal? Adama a Aničku z Alekšiniec. Pozorný riešiteľ si môže všimnúť, že máme k dispozícii \(13\) mužských mien, \(11\) ženských mien a \(7\) obcí. Tieto sa pri postupnom zvyšovaní vstupu neustále cyklia. A vďaka tomu sa postupne vystrieda všetkých \(1001\) možností.
Riešenie? Hrubá sila. Borisa dostaneme z \(1\) a potom z každého trinásetho čísla. Tak teda postupne pripočítavame \(13\). Keď to spravíme 2-krát (\(27\)), dostaneme Borisa a Filoménu z Gánoviec. Kombinácia muža a obce sa však opakuje iba raz za \(13*7 = 91\) krokov. Teda pripočítavame \(91\), kým nedostaneme v strede Hanku. Je to pri \(755\).
Ak by vás zaujímal všeobecnejší spôsob ako riešiť podobné úlohy, kľúčový pojem je "Čínska zvyšková veta".
Záver
Časom (pár týždňov po odovzdaní) sa tento text ešte doplní štatistikami ohľadne počtu pokusov pre jednotlivé úlohy. Dúfam, že ste sa pri riešení Zwarte Doos zabavili, vzoráky pochopili a že sa tešíte na Zwarte Doos 2.
riešiteľa↩
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ť.
-
Marián Horňák
odoslané 16. december 2016 18:09Test
Marián Horňák
$\frac{1}{3}$