2. Receptomaty vzorové riešenie

Zadanie

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Adamovi Královi na [email protected]

Čarodejnice (a čarodejníci) z Praskbury, ako všetky ostatné čarodejnice (a čarodejníci) po celom svete, varia kúzla. Veľmi im to ale nejde, pretože recepty sú zložité a nedávajú veľmi zmysel. Jednotlivé kroky sú však jednoduché, buď je to nejaký postup (ako zohriať, schladiť) alebo pridať ingredienciu. Je však veľmi dôležité, v akom poradí sa ingrediencie do kotla hodia a poradie krokov. Napriklad recepty “aab” a “aba” síce vyzerajú podobne, ale jeden vytvorí elixír neviditeľnosti a druhý výbuch o sile 3 megatony.

Čarodejnice sa už dostali do bodu, kedy sa boja úplne variť. Nevedia o svojich receptoch povedať, čo z nich vyjde. Pri revízii skladu posledný týždeň našli dole v sklade obrovskú knihu “Receptomaty”. Dokáže o recepte povedať, ci navarí správne kúzlo alebo nie. Receptomat môže vyzerať napríklad takto:

Tento konkrétny receptomat overuje správnosť elixíru na neviditelnosť, ktorý bol spomenutý vyššie.

Na konci knihy zo skladu našli čarodejníci kapitolu “Teória receptomatov”. Tú vám oskenovali a zdieľali na tejto adrese. Aby vám pomohli ešte viac, dokázali podľa knihy zostrojiť aj simulátor receptomatu. Ten je na tejto adrese.

Úloha

Niektoré strany z knihy receptomatov chýbajú. Pomôžte nájsť:

1. (1 bod) Receptomat pre recept “abca”.

2. (2 body) Receptomat pre recepty, ktoré obsahujú iba znaky “a”.

3. (3 body) Receptomat, ktorý akceptuje recepty v tvare čísla deliteľného číslom 3.

4. (3 body) Receptomat, ktorý akceptuje recepty s podreťazcom “abac”.

5. (3 body) Receptomat, ktorý akceptuje len abecedne usporiadané recepty (vzostupne).

6. (3 body) Aké recepty akceptuje tento receptomat? Dokážeš znížiť počet jeho stavov (množina správnych receptov musí ostať nezmenená)?

Podúlohy a, b, d, e, f sú z kapitoly “Písmenné receptomaty”. V týchto receptoch sa používajú len znaky ‘a’, ‘b’, ‘c’ a ‘d’. Podúloha c je z kapitoly “Číselné receptomaty”. V týchto sa používajú znaky ‘0’ až ‘9’.

1. (1 body) Automat pre túto úlohu bol podobný ako v zadaní príkladu, jediná zmena bol akceptovaný recept (“abca” miesto “aab”).

2. (2 body) Je diskutovateľné, či recept dĺžky 0 sa skladá iba z “a”. Formálne môžeme povedať, že pre všetky kroky receptu “” (prázdny recept) platí, že sú “a”. Uznávané sú však aj receptomaty, ktoré neakceptujú prázdne recepty. Na riešenie nám teda stačí spraviť takýto cyklus:

3. (3 body) Pre túto úlohu je dôležité si uvedomiť, ako funguje deliteľnosť tromi (ciferný súčet musí byť deliteľný tromi). Majme teda číslo, ktorého ciferný súčet je zvyšku 2 po delení 3. Pripojíme teraz k nemu číslo, ktoré dáva 1 po delení 3. Súčet 2+1 je 3 a teda po delení tromi bude ciferný súčet nulový. Príklad: 104 dáva zvyšok 2 po delení tromi. Ak pripojíme 1 (máme teda 1041), dostaneme číslo deliteľné 3. Model receptomatu, ktorý takto funguje, vyzerá takto:

4. (3 body) Ak by sa podreťazec skladal len zo znakov, ktoré sa neopakujú (napr. “abdc”), bola by táto úloha jednoduchšia. Riešením by bolo cykliť sa v počiatočnom stave a pri reťazci, ktorý obsahuje daný podreťazec by sme len išli do ďalšieho stavu vždy po jednom znaku.

Keďže v podreťazci sa 2 krát nachádza znak “a”, pri prechádzaní receptu potrebujeme rátať s tým, že dané a je už začiatok iného podreťazca, ale tiež aj s tým že predošlý podreťazec môže ešte skončiť (napr. “ababacac”). Riešenie teda musí obsahovať prechody tak, aby rátalo s možnosťou nového reťazca. Správne riešenie teda vyzerá takto:

5. (3 body) V tejto úlohe si v každom stave budeme pamätať, aký najnižši znak doteraz bol. Pri znaku s vyššou hodnotou prejdeme prechodom do ďalšieho stavu.

6. (3 body) Automat je postavený ako 2 rovnaké časti za sebou, teda časť {1} a {3} je rovnaká ako {2} a {0} (až na počiatočný stav). Chceme teda spraviť automat ako jedna z tých častí, ale musíme to prepojiť tak, aby sme akceptovali aj prázdny recept (pretože aj pôvodný automat ho akceptuje). Riešenie teda vyzerá takto: