Matematická olympiáda – kategorie P

Zadání úloh domácího kola 48. ročníku

P-I-1 Kódovací mřížka

Jednou z kódovacích metod pro předávání zpráv je použití kódovací mřížky. Zpráva se s jejím použitím zapisuje do čtvercové tabulky o 2N řádcích a sloupcích. Kódovací mřížka, která má na smluvených místech N2 výřezů, se položí na tabulku a přes výřezy můžeme zapsat znaky zprávy do řádků shora dolů a v řádku je zapisujeme zleva doprava. Mřížku je možno položit na tabulku ve 4 různých pozicích tak, že ji otočíme vždy o 90o doprava. Každá pozice v tabulce musí být správnou mřížkou odkryta popsaným způsobem přesně jednou.

Napište program MRIZKA, který co nejrychleji zjistí, zda předloženou mřížku lze použít jako kódovací.

Vstupní soubor MRIZKA.IN obsahuje 2N+1 řádků. Na prvním řádku je celé kladné číslo N (N <= 20). Každý z následujících 2N řádků obsahuje přesně 2N znaků 0 (není výřez) nebo 1 (je výřez) oddělených jednou mezerou. Výstupní soubor MRIZKA.OUT bude obsahovat jediný řádek, na kterém bude napsáno ANO, představuje-li vstupní soubor kódovací mřížku, v opačném případě na něm bude napsáno NE.

Příklad

MRIZKA.IN

2 0 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0

MRIZKA.OUT

ANO

P-I-2 Tajemný kryptogram

Popisovaný šifrovací systém vychází z reálného systému používaného za 1. světové války. Po dobytí nepřátelského štábu v něm byla nalezena tabulka č. 1, která měla 7 sloupců a 7 řádků. V jednotlivých políčkách tabulky bylo zapsáno 49 písmen a číslic. Její řádky a sloupce byly pojmenovány písmeny.


Tabulka č. 1
ADFGVMX
AZ3ENVÓA
DYÉĚČĎŠÍ
FDH82OŘ0
GJPQX7ŤG
VWRKFÁÚ1
MISUM4ŽT
X6C95BŮL

U tabulky byl proužek papíru s nějakou zašifrovanou zprávou.
DFAA VMVM AVXF DXDA VGGV FDXG
Dále byla nalezena tabulka č. 2, o které víte, že v záhlaví mohou být jednotlivé sloupce označeny navzájem různými písmeny z abecedy. Bohužel, spodní část tabulky byla nečitelná, protože byla rozmáčena vodou.


Tabulka č. 2
VYHREJ
VFVDDA




Pokuste se nalezenou zprávu dešifrovat.

Soutěžní úloha

  1. Určete systém zašifrování a dešifrování.
  2. Určete text původní (nezašifrované) zprávy.
  3. Způsobuje zašifrování nárůst délky zprávy? Jestliže ano, jaký je faktor nárůstu?
  4. Sestavte program, který má v sobě zakódovánu tabulku č. 1. Jeho vstupní data jsou:
    • otevřený (nezašifrovaný) původní text ukončený znakem #
    • záhlaví tabulky č. 2 ukončené rovněž znakem # (v našem případě je to řetězec "VYHREJ#"
    • výstupem je zašifrovaná zpráva (v našem případě je to řetězec "DFAA VMVM AVXF DXDA VGGV FDXG")

P-I-3 Hra se zápalkami

Dva hráči hrají následující hru. Na začátku hry jsou dány tři hromádky zápalek, přičemž na každé hromádce je položen předem pevně určený počet zápalek (hromádka může být i prázdná). Poté se oba hráči střídají ve svých tazích, přičemž začíná první hráč. V jednom tahu si hráč vybere libovolnou hromádku, na které je alespoň jedna zápalka, a odebere z ní nenulový počet zápalek. Hra probíhá tak dlouho, dokud je v alespoň jedné hromádce nenulový počet zápalek. Hráč, který nemá tah, prohrává partii.

Napište program, který pro dané počty zápalek zjistí, zda existuje vítězná strategie pro prvního hráče, a v kladném případě nalezne pro prvního hráče jeho nejlepší počáteční tah.

Vstupem programu bude textový soubor INPUT.TXT. Tento soubor bude obsahovat celkem $N$ různých počátečních pozic (1 <= N <= 20). Číslo N bude uvedeno v prvním řádku. V dalších N řádcích bude uvedena vždy trojice čísel a,b,c, která bude vždy označovat počty zápalek na jednotlivých hromádkách. Můžete předpokládat, že čísla a, b, c budou vždy celá a platí 0 <= a,b,c <= 255. Výstupem programu bude textový soubor OUTPUT.TXT, který bude obsahovat celkem N řádků. Každý řádek bude odpovídat příslušné trojici čísel a, b, c uvedené v souboru INPUT.TXT. Tento řádek buď bude obsahovat řetězec 'NE', jestliže v dané pozici neexistuje vítězná strategie pro prvního hráče, nebo bude obsahovat trojici čísel x, y, z, která vznikne po provedení nejlepšího počátečního tahu prvního hráče v případě, že pro něj bude existovat vítězná strategie.

Příklad

INPUT.TXT

2 1 6 1 1 1 0

OUTPUT.TXT

1 0 1 NE Poznámka: Existuje algoritmus, který vyřeší úlohu v konstantním čase.

P-I-4 Normální algoritmy Markova

Konečnou množinu symbolů T={a0,a1,..., an} nazveme abecedou. Prvky množiny T budeme nazývat znaky abecedy. Slovem P v abecedě T nazveme každou konečnou posloupnost znaků abecedy T. Prázdné slovo budeme označovat symbolem _. Algoritmem v abecedě T budeme rozumět funkci, jejíž definičním oborem je podmnožina slov v abecedě T a oborem hodnot je opět podmnožina slov v T. Nechť P je slovo v abecedě T. Řekneme, že algoritmus A je přípustný pro slovo P, právě když P je prvkem jeho definičního oboru. Většinu algoritmů je možno rozdělit na nějaké jednodušší kroky. Jeden ze způsobů navrhl v roce 1954 A. A. Markov. Základní operací je substituce jednoho slova za jiné. Výrazy P-> Q a P->. Q, kde P a Q jsou slova v abecedě T, nazýváme formulemi substituce v abecedě T. Přitom předpokládáme, že šipka (->) a tečka (.) nejsou prvky T. Některé ze slov P a Q může být i prázdné. Formuli P-> Q nazýváme obyčejnou a formuli P->. Q nazýváme koncovou. Zápisem P->(.)Q rozumíme buď formuli P-> Q, nebo P->. Q. Konečný seznam formulí substituce v abecedě T
P1 -> (.)Q1
P2 -> (.)Q2
...
Pr -> (.)Qr
nazýváme schéma algoritmu A.

Řekneme, že slovo W je obsaženo ve slově Q, právě když existují taková slova U, V (mohou být i prázdná), že Q=UWV. Algoritmus A pracuje následujícím způsobem. Nechť je dáno slovo P v abecedě T. Ve schématu algoritmu A najdeme první formuli Pm ->(.)Qm (1 <= m <= r) takovou, že Pm je obsaženo v P. Provedeme substituci nejlevějšího výskytu slova Pm na Qm. Označme R1 slovo, které je výsledkem této substituce. Můžeme napsat A: P|-R1. Je-li Pm ->. Qm koncová formule substituce, činnost algoritmu A končí, jeho hodnotou je slovo R1 a píšeme A(P)=R1. Je-li Pm -> Qm obyčejná formule substituce, aplikujeme na R1 stejný postup, který jsme použili na slovo P. Tímto způsobem pokračujeme dále. Dostaneme posloupnost slov P,R1,...,Ri (i >= 1). Můžeme psát
A: P |- R1,...,|- Ri
nebo též zkráceně
A: P |-> Ri
Jestliže v určitém okamžiku nastane situace, že ani jedno ze slov P1,...,Pr není obsaženo v Ri, potom činnost algoritmu rovněž končí a Ri je hodnotou algoritmu A. Může se ovšem stát, že popsaný postup nikdy nekončí. V takovém případě řekneme, že algoritmus není přípustný pro slovo P.

Příklad 1

Nechť T={b,c}. Uvažujme schéma:
b -> . _
c -> c
normálního algoritmu A pro slovo P v abecedě T.

Výsledek činnosti algoritmu A je pro P následující:

Příklad 2

Nechť T={a0,a1,...,an}. Uvažujme schéma
a0 -> _
a1 -> _
...
an -> _
Takové schéma zapisujeme zkráceně ve tvaru:
x->_ (x prvkem T)
Při tomto zkráceném zápisu schématu předpokládáme, že odpovídající prvky seznamu mohou být zapsány v libovolném pořadí. Výsledkem algoritmu A je vždy prázdné slovo. Říkáme též, že A přepisuje libovolné slovo (v abecedě T) na prázdné slovo. Činnost tohoto algoritmu můžeme zapsat například ve tvaru A:a1a3a0 |- a1a3 |- a3 |- _ nebo A:a1a3a0 |-> _, takže A(a1a3a0)=_.

Příklad 3

Nechť T={1}. Definujme induktivně [0]=1 a [n+1]=[n]1, tj. [1]=11, [2]=111 atd. Slova [n] nazveme čísla.

Uvažujme schéma
_ ->. 1
Pro libovolné slovo P v T platí zřejmě A(P)=1P, což můžeme zapsat ve tvaru A([n])=[n+1] pro libovolné přirozené číslo n. (Uvědomte si, že každé slovo P začíná prázdným slovem _, tj. P=_ P).

Abecedu B nazveme rozšířením abecedy T, je-li T podmnožinou B. V řadě případů je nutno při konstrukci schématu algoritmu v abecedě T použít mimo znaků abecedy T ještě další pomocné znaky. Pak řekneme, že jsme vytvořili schéma algoritmů nad abecedou T (tj. v nějaké abecedě B, která je rozšířením T).

Příklad 4

Nechť T={a0,a1,...,an} je abeceda. Pro každé slovo P=aj0aj1...ajk v T (k >= 0, aji je prvkem T, i=0,1,...,n) je slovo P-1=ajk...aj1aj0 obrácením slova P. Sestrojte normální algoritmus A, který pro libovolné slovo P vytvoří jeho obrácení, tj. A(P)=P-1.

Uvažujme zkrácené schéma algoritmu v abecedě B=TU{b1,b2}:
(a) b1b1->b2
(b) b2x->xb2 (x prvkem T)
(c) b2b1->b2
(d) b2->. _
(e) b1yx->x b1 y (x,y prvky T)
(f) _->b1

Tím jsme popsali činnost normálního algoritmu A nad abecedou T obracející slovo v abecedě T.

Soutěžní úlohy

  1. Nechť H={1}, M={1,*}. Každé přirozené číslo n může být zapsáno jako [n], což je slovo v abecedě H (viz př. 3 ve studijním textu). Napište schéma algoritmu A v M, který je přípustný pouze pro slova, jež jsou zápisem přirozeného čísla. Hodnotou algoritmu A pro libovolné [n] bude A([n])=[0]. Zdůvodněte správnost navrženého algoritmu.
  2. Je dána abeceda T, která neobsahuje znaky b1, b2, b3, B=TU{b1,b2,b3}. Sestrojte schéma algoritmu A v abecedě B, který každé slovo v abecedě T zdvojí (tj. A(P)=PP). Zdůvodněte jeho správnost.