Matematická olympiáda – kategorie P

Zadání úloh ústředního kola 43. ročníku

P-III-1

 Souvislý úsek v posloupnosti celých čísel nazveme vybalancovaným úsekem, jestliže počet kladných a počet záporných čísel v úseku se sobě rovnají.

Je dáno celé číslo N (1<=N<=1000) a posloupnost N celých čísel. Napište program, který určí délku maximálního vybalancovaného úseku v dané posloupnosti čísel. Při návrhu programu se zaměřte na dosažení co největší rychlosti výpočtu.

Příklad: Pro N=10 a posloupnost čísel 8 6 4 7 -5 -3 2 0 -1 9 bude výsledkem číslo 7, neboť nejdelší vybalancovaný úsek 4 7 -5 -3 2 0 -1 (případně jiný stejně dlouhý vybalancovaný úsek 7 -5 -3 2 0 -1 9) je tvořen sedmi čísly.

P-III-2

V zemi je N měst označených čísly od 1 do N. Mezi městy je vybudována silniční síť. Každá silnice spojuje vždy dvojici měst. Všechny silnice jsou obousměrné. Mezi některými dvojicemi měst přímá silnice nevede, ale z každého města je možné dojet po silnicích do libovolného jiného města (třeba i více různými způsoby). Všechna případná křížení silnic mimo města jsou mimoúrovňová (pomocí mostů) a neumožňují vozidlům přejet z jedné silnice na druhou.

Silnici nazveme nepostradatelnou, pokud by se jejím zničením úplně přerušilo silniční spojení mezi některou dvojicí měst.

Napište program, který vyhledá a vypíše všechny nepostradatelné silnice. Vstupem programu je počet měst N a dále seznam všech silnic vedoucích mezi městy. Každá silnice je zadána dvojicí čísel měst, mezi nimiž vede.

P-III-3

Na hromádce je připraven předem známý počet N zápalek, kde N je liché číslo. Dva hráči hrají hru, při které z hromádky střídavě odebírají zápalky. Hráč, který je na řadě, musí v jednom tahu odebrat 1, 2 nebo 3 zápalky. Hra skončí, když je celá hromádka zápalek rozebraná. Vyhrává ten hráč, který z hromádky celkově odebral sudý počet zápalek.

  1. Určete, pro jaké hodnoty N má při správné hře zajištěnu výhru ten hráč, který je právě na tahu. Jak musí během hry postupovat, aby této výhry dosáhl? Své tvrzení zdůvodněte.

  2. Řešte stejnou úlohu pro případ, že hráč smí v jednom tahu odebrat z hromádky 1, 2, 3 nebo 4 zápalky.

P-III-4

 Konečný sekvenční stroj je speciální výpočetní zařízení. Má řídicí jednotku, čte několik vstupních sledů a vytváří jeden výstupní sled. Počet vstupních sledů k je pro každý sekvenční stroj pevně dán. Sledem zde rozumíme konečnou posloupnost znaků z předem dané konečné množiny (tzv. abecedy). Každý vstupní sled je čten postupně znak po znaku zleva doprava, žádný znak ze vstupního sledu nemůže být přečten vícekrát.

Řídicí jednotka má konečnou paměť; říkáme, že se může nacházet v jednom z konečně mnoha stavů. Programem stroje je sada přechodových pravidel, která každému vnitřnímu stavu a k-tici vstupních znaků (z každého vstupního sledu jeden znak) přiřazují nový vnitřní stav a výstupní znak.

Výpočet stroje probíhá po krocích. Na začátku výpočtu je stroj v počátečním stavu a z každého vstupního sledu bude číst první znak. V jednom kroku stroj přečte z každého vstupního sledu po jednom znaku, podle vhodného přechodového pravidla (tj. podle svého programu) změní svůj vnitřní stav a zapíše nejvýše jeden znak na výstup. Výpočet končí v okamžiku, kdy neexistuje přechodové pravidlo, podle něhož by výpočet mohl pokračovat.

Nyní popíšeme sekvenční stroj ještě jednou formálněji. Konečný sekvenční stroj s k vstupy je uspořádaná pětice (V,Y,Q,f,q0), kde V,Y,Q jsou konečné množiny, q0 je prvkem Q a f je parciální zobrazení Qx(VU{_})k -> Qx(YU{_}). Slovo parciální znamená, že f nemusí být definováno pro všechny kombinace stavů a vstupních symbolů (tzn. v takové situaci není určeno, jak má výpočet pokračovat). Množina V se nazývá vstupní abeceda, Y výstupní abeceda, Q je množina stavů, q0 je počáteční stav a f jsou přechodová pravidla. Speciální hodnota _ použitá v definici přechodových pravidel znamená, že v příslušném vstupním sledu už není žádný znak (celý vstupní sled už byl přečten) resp. že se do výstupního sledu v tomto kroku nic nezapíše.

Výpočet stroje začíná ve stavu q0 a vstupní sledy jsou nastaveny pro čtení prvních znaků. V každém kroku výpočtu stroj přečte po jednom znaku z těch vstupních sledů, které ještě nebyly přečteny do konce, vypíše jeden (případně žádný) znak do vytvářeného výstupního sledu a změní svůj vnitřní stav. Označme q momentální stav stroje a a1, a2...ak právě čtené znaky ve vstupních sledech (je-li některý vstupní sled již celý přečten, bude čteným znakem _). V přechodových pravidlech se vyhledá hodnota f(q,a1,a2...ak)=(q',y). Pokud je nalezena, stroj do výstupního sledu zapíše znak y a přejde do stavu q'. Pokud odpovídající přechodové pravidlo neexistuje, výpočet stroje končí.

Pomocí sekvenčních strojů budeme zpracovávat zápisy celých nezáporných čísel. Zápisem celého nezáporného čísla C v poziční soustavě o základu (-2) je sled znaků anan-1...a1a0 z abecedy {0,1} takový, že platí:
C=an(-2(n+an-1(-2)n-1+...+ a1(-2)1+a0(-2)0
Jednotlivým znakům zápisu říkáme cifry. Takovýto zápis čísla je strojem čten nebo je vytvářen postupně od nejvyšších řádů (an) k nejnižším (a0). Zápisem pozpátku rozumíme zápis cifer v opačném pořadí. Čísla zapsaná pozpátku tedy stroj čte v pořadí od nejnižších řádů (a0) k nejvyšším (an).

Uvědomte si, že popsaným způsobem lze zapsat libovolné celé číslo, a to až na úvodní nuly právě jedním způsobem.

Příklad zápisu čísel v poziční soustavě o základu -2

+3 lze zapsat jako 111, 0111 nebo také 0000000000111
-3 lze zapsat jako 1101, 01101 nebo také 00000000001101

Soutěžní úloha

  1. Sestavte konečný sekvenční stroj se dvěma vstupy, který porovná vstupující čísla podle velikosti. Vytiskne S, pokud jsou stejná, P pokud je první větší a D, pokud je druhé větší.

  2. Řešte úlohu a pro případ, kdy jsou čísla zapsaná pozpátku.

  3. Sestavte konečný sekvenční stroj se dvěma vstupy, který vytiskne součet vstupujících čísel.

  4. Řešte úlohu c pro případ, kdy jsou čísla zapsaná pozpátku.

  5. Sestavte konečný sekvenční stroj s jedním vstupem, který určí, zda je vstupní číslo dělitelné třemi. Výstupem bude znak A pokud je dělitelné třemi, v opačném případě bude výstupem znak N.

  6. Sestavte konečný sekvenční stroj s jedním vstupem, který spočítá celočíselný podíl při dělení vstupujícího čísla třemi.

Ve všech úlohách předpokládejte, že čísla jsou ve vstupních sledech zapsána v poziční soustavě o základu (-2). Pokud dospějete k názoru, že některý ze strojů nelze sestrojit, své tvrzení zdůvodněte.