Matematická olympiáda – kategorie P

Zadání úloh oblastního kola 43. ročníku

P-II-1

Souvislý úsek v posloupnosti celých čísel nazveme K-hladkým úsekem, jestliže se libovolná dvojice čísel, která do něj patří, liší nejvýše o K.

Jsou dána dvě kladná celá čísla N, K a posloupnost N celých čísel. Napište program, který určí délku maximálního K-hladkého úseku v dané posloupnosti čísel. Počet čísel N není předem shora omezen a může být velmi vysoký, naproti tomu hodnota K je rovna nejvýše 10. Při návrhu programu se zaměřte na dosažení co největší rychlosti výpočtu.

Příklad: Pro N=10, K=2 a posloupnost čísel 2 1 2 3 3 4 3 4 6 4 bude výsledkem číslo 6, neboť nejdelší 2-hladký úsek 2 3 3 4 3 4 je tvořen šesti čísly (další 2-hladké úseky, např. 2 1 2 3 3 nebo 4 6 4, jsou kratší).

P-II-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.

Napište program, který určí, zda je možné rozdělit města do dvou skupin tak, aby každá dvojice měst patřících do stejné skupiny byla spojena přímou silnicí (tzn. uvnitř každé skupiny vede přímá silnice mezi každými dvěma městy). Nezáleží přitom na velikosti jednotlivých skupin (jedna ze skupin může být případně i prázdná), ale každé město musí být do některé skupiny zařazeno.

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-II-3

Na hromádce je připraven předem známý počet N zápalek. 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 takový počet zápalek, který je celočíselnou mocninou dvou (tzn. lze ho vyjádřit ve tvaru 2Kpro vhodné celé nezáporné číslo K). Vyhrává ten hráč, který vezme z hromádky poslední zápalku.

  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 počet zápalek odebíraných v jednom tahu musí být tvaru 3K pro nějaké celé nezáporné číslo K.

P-II-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 binární (dvojkové) poziční soustavě je sled znaků anan-1...a1a0 z abecedy {0,1} takový, že platí:

  1. buď n=0 (tj. zápis je tvořen jediným znakem), nebo n>0 a přitom an=1 (víceznakový zápis začíná vždy znakem 1)
  2. C=an2n+an-12n-1+...+ a121+a020
Jednotlivým znakům zápisu říkáme binární 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).

Pomocí sekvenčních strojů budeme nyní zpracovávat zápisy celých čísel v tzv. doplňkovém kódu. K zápisu čísel budeme používat abecedu {0,1}. Celá nezáporná čísla budeme zapisovat v obvyklé binární poziční soustavě s jedinou drobnou úpravou - zápis čísla musí začínat číslicí 0. Toho lze snadno dosáhnout doplněním jedné nebo více nul zleva k zápisu čísla. Každé celé nezáporné číslo má tedy nekonečně mnoho různých zápisů, které se liší pouze počtem úvodních nul.

Zápisy záporných čísel získáme následujícím postupem. Ze zápisu absolutní hodnoty čísla (v binární soustavě s vedoucí nulou) nejprve odečteme jedničku a potom zaměníme každou 0 za 1 a každou 1 za 0. Zápisy záporných čísel tedy začínají číslicí 1. I každé záporné číslo má více možných zápisů, ty se liší pouze počtem úvodních jedniček.

Příklad zápisu čísel v doplňkovém kódu

+3 lze zapsat jako 011, 0011 nebo také 000000000011
-3 lze zapsat jako 101, 1101 nebo také 111111111101

Soutěžní úloha

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

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

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

  4. 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 doplňkovém kódu. Pokud dospějete k názoru, že některý ze strojů nelze sestrojit, své tvrzení zdůvodněte.