2. Preblšený cirkus sa vracia

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Edovi “Baklažánovi” Batmendijnovi na [email protected]

Pamätáte si ešte na blší cirkus?¹ V tomto cirkuse majú obzvlášť veľké blchy, ktoré sa dajú trénovať. Minulý týždeň sa blšiemu cirkusu podarilo vyšľachtiť nový druh bĺch, ktoré sú ešte inteligentnejšie než tie staré a dajú sa s nimi robiť ešte zložitejšie predstavenia.

Pred blším vystúpením sa na zem nakreslí niekoľko (nepretínajúcich sa) kruhov a nejaké šípky medzi nimi. Každá šípka vedie od nejakého kruhu do nejakého (možno aj toho istého) kruhu. Ku každej šípke sa napíše buď jeden znak (písmeno alebo číslica), alebo sa nechá neoznačená, pričom musí platiť nasledovná vlastnosť: zo žiadneho kruhu nevedú von dve šípky označené rovnakým znakom, ani dve neoznačené šípky. Okrem toho sa jeden kruh označí ako štartovací a niektoré kruhy sa označia ako víťazné. Celé toto rozostavenie kruhov a šípok budeme nazývať schéma .

Samotné predstavenie vyzerá nasledovne: na začiatku sa jedna blcha postaví do štartovacieho kruhu a krotiteľ vyzve niektorého z divákov, aby mu niečo (v závislosti od druhu prestavenia to môže byť postupnosť písmen alebo číslic) napísal na papier. Toto niečo budeme nazývať vstupný text. Následne krotiteľ vstupný text nahlas číta znak po znaku. Vždy, keď krotiteľ prečíta nejaký znak, blcha urobí nasledovné:

• Najprv sa pozrie, či z kruhu, v ktorom práve stojí, vedie nejaká šípka označená znakom, ktorý krotiteľ práve prečítal. Ak áno, blcha skočí do kruhu, do ktorého vedie táto šípka.
• V prípade, že z kruhu kde blcha stála, neviedla žiadna šípka označená práve prečítaným znakom, blcha sa pozrie, či z neho vedie aspoň neoznačená šípka. Ak áno, blcha skočí pozdĺž tejto šípky.
• V prípade, že z kruhu kde blcha stála neviedla ani neoznačená šípka, blcha sa na to vykašle, vyskočí von z kruhu a predstavenie sa predčasne skončí.

Na konci predstavenia sa krotiteľ pozrie, v ktorom kruhu blcha skončila. Ak skončila v niektorom z víťazných kruhov, zablahoželá divákovi a dá mu lízatko.

Všimnite si, že to, v ktorom kruhu blcha skončí závisí iba na schéme a na vstupnom texte. Ak si teda vezmeme jednu konkrétnu schému, je pre ňu jednoznačne určené, pri ktorých vstupných textoch skončí blcha v niektorom z víťazných kruhov. Tieto vstupné texty budeme nazývať víťazné pre danú schému. V tejto úlohe budeme pre zadané množiny víťazných vstupných textov kresliť schémy.

Príklad

Skúsme nakresliť schému, pre ktoré sú víťazné všetky čísla deliteľné tromi (ktoré môžu prípadne začínať zbytočnými nulami) a už nič iné. Vieme, že číslo je deliteľné tromi práve vtedy, keď je jeho ciferný súčet deliteľný tromi. Ak by si teda blcha vedela pamätať, aký je súčet prečítaných cifier a na konci podľa toho skočiť do správneho kruhu, mali by sme vyhrané. Dokonca by nám stačilo, aby si stále pamätala, aký zvyšok dáva súčet doteraz prečítaných cifier po delení tromi. Ak by bol tento zvyšok na konci nula, blcha by skočila do nejakého víťazného kruhu, inak by skočila do nejakého iného kruhu.

Blcha si, žiaľbohu, počas predstavenia nič nepamätá. Informáciu o zvyšku ciferného súčtu po delení tromi však môžeme mať počas predstavenia zakódovanú v pozícii blchy (teda v tom, v ktorom kruhu sa blcha práve nachádza). Môžeme teda nakresliť schému, ktorá bude mať tri kruhy (označme ich 0, 1 a 2). Pritom bude platiť, že:

• V kruhu 0 bude blcha vtedy, keď je súčet doteraz prečítaných cifier deliteľný tromi.
• V kruhu 1 bude blcha vtedy, keď súčet doteraz prečítaných cifier dáva zvyšok 1 po delení tromi.
• V kruhu 2 bude blcha vtedy, keď súčet doteraz prečítaných cifier dáva zvyšok 2 po delení tromi.

Z každého kruhu potom pôjde von 10 šípok označných ciframi 0 až 9. Šípky označené 0, 3, 6 a 9 budú vždy viesť do toho istého kruhu, lebo pripočítaním 0, 3, 6 alebo 9 sa zvyšok po delení troma nezmení. Šípky označené 1, 4 a 7 budú vždy viesť do kruhu s o 1 väčším číslom (resp. z kruhu 2 do kruhu 0), lebo pripočítaním 1, 4 alebo 7 sa zvyšok po delení tromi zvýši o 1. Nakoniec, šípky označené 2, 5 a 8 budú viesť do kruhu s o 1 nižším číslom (resp. z kruhu 0 do kruhu 2). Za štartovací označíme kruh 0, lebo keď sme ešte nič neprečítali, súčet prečítaných cifier je 0. Jediným víťazným kruhom bude opäť kruh 0, lebo číslo je deliteľné tromi vtedy, keď jeho ciferný súčet dáva po delení tromi zvyšok 0.

Súťažná úloha

1. (5 bodov) Nakreslite schému, pre ktorú budú víťazné všetky postupnosti znakov zložené z písmen "a", "b" a "c" také, že žiadne dve za sebou idúce písmená nie sú rovnaké. Žiadne iné postupnosti už víťazné byť nemajú. Teda napríklad postupnosť "abcbcbcbaba" má byť víťazná, ale postupnosť "bacca" nemá byť víťazná.

2. (5 bodov) Nakreslite schému, pre ktorú budú víťazné postupnosti znakov, v ktorých sa niekde vyskytujú 4 á-čka po sebe. Teda napríklad slovo "tadaaaa" má byť víťazné, ale slovo "lalalalalala" nemá byť víťazné.

3. (5 bodov) Nakreslite schému, pre ktorú budú víťazné postupnosti znakov, v ktorých sa niekde (súvislo) vyskytuje slovo "tamtamtatam"² (pozor, nie slovo "tamtamtamtam"). Slovo "alotamtamtatambetam" je víťazné, ale slovo "tamverutamtatamtam" víťazné nie je.

V každej podúlohe okrem nakreslenia schémy aj zdôvodnite, prečo budú pre túto schému víťazné všetky postupnosti znakov špecifikované v danej podúlohe a prečo už žiadna iná postupnosť nebude víťazná. Nezabudnite vo vašich schémach vyznačiť štartovací kruh a víťazné kruhy.