Matematická olympiáda – kategorie P

Zadání úloh školní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 N² 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 90^o 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
	A	D	F	G	V	M	X
A	Z	3	E	N	V	Ó	A
D	Y	É	Ě	Č	Ď	Š	Í
F	D	H	8	2	O	Ř	0
G	J	P	Q	X	7	Ť	G
V	W	R	K	F	Á	Ú	1
M	I	S	U	M	4	Ž	T
X	6	C	9	5	B	Ů	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
V	Y	H	R	E	J
V	F	V	D	D	A

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={a₀,a₁,..., a_n} 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
P₁ -> (^.)Q₁
P₂ -> (^.)Q₂
...
P_r -> (^.)Q_r
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 P_m ->(^.)Q_m (1 <= m <= r) takovou, že P_m je obsaženo v P. Provedeme substituci nejlevějšího výskytu slova P_m na Q_m. Označme R₁ slovo, které je výsledkem této substituce. Můžeme napsat A: P|-R₁. Je-li P_m ->^. Q_m koncová formule substituce, činnost algoritmu A končí, jeho hodnotou je slovo R₁ a píšeme A(P)=R₁. Je-li P_m -> Q_m obyčejná formule substituce, aplikujeme na R₁ stejný postup, který jsme použili na slovo P. Tímto způsobem pokračujeme dále. Dostaneme posloupnost slov P,R₁,...,R_i (i >= 1). Můžeme psát
A: P |- R₁,...,|- R_i
nebo též zkráceně
A: P |-> R_i
Jestliže v určitém okamžiku nastane situace, že ani jedno ze slov P₁,...,P_r není obsaženo v R_i, potom činnost algoritmu rovněž končí a R_i 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í:

• Je-li P prázdné slovo, je hodnota algoritmu rovněž prázdné slovo (A(_)= _).
• Obsahuje-li P aspoň jeden znak b, potom hodnotou algoritmu je slovo, které vznikne z P vynecháním nejlevějšího výskytu znaku b v P (např. A(cbcb)=ccb).
• Algoritmus není přípustný pro slova neobsahující znaky b.

Příklad 2

Nechť T={a₀,a₁,...,a_n}. Uvažujme schéma
a₀ -> _
a₁ -> _
...
a_n -> _
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:a₁a₃a₀ |- a₁a₃ |- a₃ |- _ nebo A:a₁a₃a₀ |-> _, takže A(a₁a₃a₀)=_.

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={a₀,a₁,...,a_n} je abeceda. Pro každé slovo P=a_j0a_j1...a_jk v T (k >= 0, a_ji je prvkem T, i=0,1,...,n) je slovo P^-1=a_jk...a_j1a_j0 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{b₁,b₂}:
(a) b₁b₁->b₂
(b) b₂x->xb₂ (x prvkem T)
(c) b₂b₁->b₂
(d) b₂->^. _
(e) b₁yx->x b₁ y (x,y prvky T)
(f) _->b₁

• Na základě formule (f) dostaneme A:P |- b₁ P.
• Potom je aplikována v potřebném počtu opakování formule (e): A: P |- a_j1b₁ a_j0a_j2... a_jk |- a_j1a_j2b₁ a_j0 a_j3...a_jk |-> a_j1a_j2 ... a_jkb₁ a_j0.
• S opakováním předchozích dvou kroků postupně dostaneme
  A: P |-> a_j2a_j3... a_jkb₁ a_j1 b₁ a_j0 |-> b₁ a_jk b₁ a_j(k-1)...b₁ a_j1b₁ a_j0 |- |- b₁b₁ a_jk b₁ a_j(k-1)...b₁ a_j1 b₁ a_j0
  
• S pomocí (a) dále dostaneme A: P |-> b₂ a_jk b₁ a_j(k-1)...b₁ a_j1 b₁ a_j0, pomocí (b) a (c) a s posledním použitím (d) dostaneme A(P)=P^-1.

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 b₁, b₂, b₃, B=TU{b₁,b₂,b₃}. 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.