2. Receptomaty

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