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
2 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
- Určete systém zašifrování a dešifrování.
- Určete text původní (nezašifrované) zprávy.
- Způsobuje zašifrování nárůst délky zprávy? Jestliže ano,
jaký je faktor nárůstu?
- 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
0,a
1,...,
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
1 -> (
.)Q
1
P
2 -> (
.)Q
2
...
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 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í:
- 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
0,a
1,...,a
n}. Uvažujme schéma
a
0 -> _
a
1 -> _
...
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
1a
3a
0
|- a
1a
3 |- a
3 |-
_ nebo A:a
1a
3a
0
|-> _, takže
A(a
1a
3a
0)=_.
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
0,a
1,...,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
{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
- Na základě formule (f) dostaneme A:P |- b1 P.
- Potom je aplikována v potřebném počtu opakování formule (e):
A: P |- aj1b1 aj0aj2...
ajk |-
aj1aj2b1 aj0
aj3...ajk |-> aj1aj2
... ajkb1 aj0.
- S opakováním předchozích dvou kroků postupně dostaneme
A: P |-> aj2aj3... ajkb1
aj1 b1 aj0 |-> b1 ajk b1
aj(k-1)...b1 aj1b1 aj0 |-
|- b1b1
ajk b1 aj(k-1)...b1 aj1
b1 aj0
- S pomocí (a) dále dostaneme
A: P |-> b2 ajk b1
aj(k-1)...b1 aj1
b1 aj0, 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
- 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.
- Je dána abeceda T, která neobsahuje znaky b1,
b2, b3, B=T
U
{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.