1. Prazvláštne artefakty

Táto úloha je špeciálna. Odovzdávaš aj popis, aj riešiš podúlohy v našom editore, za ktoré dostaneš body automaticky. Ak máš akékoľvek otázky ohľadom tejto úlohy, napíš Andrejovi na [email protected]

Táto úloha je identická s úlohou KSP - Existenčná kríza. KSP je súťaž určená najmä pre stredoškolákov, ale aj ak si mladší, tak sa môžeš kľudne skúsiť zapojiť. V tom prípade ale musíš programy aj popisy odovzdať aj na stránke Prasku, aj na stránke KSP.

MisQo nenosil respirátor a dostal existenčnú krízu. Teraz mu nedajú spať otázky ako napríklad:

• “čo je to TLB a aké má využitie?”,
• “má jazyk generovaný turingovym strojom danú netriviálnu vlasnosť?”,
• “aký bol tvoj názor na voľný program? bolo ho málo alebo veľa?”
• “kedy vyjde nový Taylor Swift album?”
• a, samozrejme, “aká je odpoveď na otázku Života, Vesmíru a Všetkého?”.

Tak sa raz MisQo jedného dňa prechádzal po Ikei, dumajúc nad týmito existenčnými otázkami, keď tu zrazu začul tiché “Pšt!” ¹. Obzrel sa, a uvidel záhadnú postavu v kabáte, ktorej nebolo vidno do tváre. Teda možno to bolo tým, že mala len pár centimetrov. Piskľavý hlas oznámil “tento počítač má všetky odpovede, ktoré hľadáš…”. MisQo s nadšením pochybný obchod prijal a domov priniesol masívnu krabicu. Keď ju však doma otvoril, čakalo ho prekvapenie. V krabici bolo iba zrkadlo a kryptický nápis “Kľúčom si ty sám…”. MisQo si to, samozrejme, vyložil tak, že všetky súčiastky budú nechcené veci, ktoré nájde vo svojom byte.

Po prehrabaní zopár kútov našiel nasledovné artefakty, z ktorých každý má nejakú ikonickú funkciu:

1. starožitný želé dávkovač (\(z\)), ktorý už dávno nemá želé. Jeho funkcia je taká, že vždy vracia \(0\).
2. inhalátor (\(i\)) plný veľmi priľnavých trblietok, ktoré skrášlia čokoľvek, čoho sa dotknú. Jeho funkcia je taká, že čokoľvek je na vstupe, vráti o \(1\) zvýšené.
3. nekonečná sada (\(s\)) zberačov odpadkov všetkých možných dĺžok. Pre každé prirodzené číslo \(n\) sa nájde nejaký zberač \(s_n\), ktorého funkcia je taká, že vráti \(n\)-tú hodnotu zo svojho vstupu.
4. odniekiaľ zo steny vytiahnutú kovovú trubku (\(K\)), do ktorej sa dá nasypať niekoľko iných artefaktov. Jej funkcia je taká, že na svojich vstupoch spustí všetky tieto artefakty, až na prvý, ktorý spustí až na konci, na výsledkoch všetkých predošlých.
5. prastarý rotor (\(R\)), na ktorý sa dá pripevniť nejaký iný artefakt, aby svoju funkciu vykonal niekoľkokrát za sebou. Jeho funkcia je taká, že zo vstupu prečíta číslo, a toľkokrát spustí na zvyšku vstupu artefakt, ktorý sa na ňom točí.

Teraz by MisQo rád zostrojil počítače, ktoré mu dajú odpovede na jeho kritické otázky. Samozrejme, s takto skromnými materiálmi to nie je vôbec triviálne. MisQovi sa veľmi nechce, a tak je na vás, aby ste pre neho tieto počítače zostrojili…

Úloha

Táto úloha sa rieši interaktívne a môžete ju riešiť tu. Tam aj nájdete podrobnejšie pokyny k tomu, ako fungujú jednotlivé artefakty a ako sa z nich dajú skladať počítače.

K tejto úlohe píšete aj popis. Pre každú podúlohu by mal popis obsahovať maximálne 5 viet, kde opíšete, čo ste vlastne urobili a prečo to funguje a screenshot programu. Nemusí obsahovať žiadnu analýzu zložitosti ani nič podobné.

Každá podúloha má 5 bodov za program a 5 bodov za popis. Body za program sa ti pripočítajú automaticky, keď odovzdáš správny program, body za popis dostaneš niekedy po konci kola.