Řešení úloh ústředního kola (1. soutěžní den) 48. ročníku
P-III-1 Šifrovací mřížka
Úlohu přetransformujeme na jednoduchou úlohu z teorie grafů.
Vytvoříme graf G, jehož vrcholy budou čísla 1,2,...,4N
2
a mezi vrcholy i a j povede hrana právě tehdy, pokud se písmeno,
které bylo v původním textu na pozici i, přemístí po zašifrování
jednou nebo druhou mřížkou na pozici j, nebo naopak,
pokud se písmeno z původní pozice j může
dostat zašifrováním pomocí některé z mřížek na pozici i.
Označme nyní symbolem P počet komponent souvislosti grafu G.
Dokážeme, že počet řetězců, které se po zašifrování oběma mřížkami
nezmění, je KP (K je počet znaků abecedy).
Mějme libovolný text t, který se po zašifrování jednou i druhou
mřížkou nezmění. Označme ti znak, který je v textu t na
i-té pozici.
Nejprve si uvědomme, že jsou-li vrcholy i a j v grafu G
spojeny hranou, potom platí ti=tj.
To vyplývá z konstrukce
grafu G - jestliže písmeno ti
přejde po zašifrování jednou nebo druhou mřížkou na pozici j,
musí být stejné jako písmeno, které bylo na pozici j v původním
textu t (jinak by se
text změnil). Podobně můžeme postupovat v případě, že naopak
tj se šifrováním dostane na pozici i.
Rozšířením této úvahy zjistíme, že pro libovolné dva vrcholy i a
j nacházející se v téže komponentě souvislosti platí, že ti=tj.
Jsou-li totiž i a j v téže komponentě, spojuje je nějaká cesta.
Každé dva po sobě jdoucí vrcholy na této cestě jsou spojeny hranou,
a proto na jim odpovídajících pozicích v t musí být stejné znaky.
Využitím tranzitivity rovnosti (jestliže ta=tb a tb=tc,
pak také ta=tc) dostaneme z těchto rovností i rovnost pro koncové
vrcholy cesty (ti=tj).
Dokázali jsme tedy, že pokud se t nezmění zašifrováním pomocí ani
jedné z mřížek, na všech pozicích z jedné komponenty souvislosti
jsou stejná písmena. Nyní dokážeme, že pokud naopak na všech
pozicích z jedné komponenty souvislosti jsou stejná písmena,
pak text t bude mít po
zašifrování jednou i druhou mřížkou na pozicích z této komponenty
původní hodnoty. Mějme tedy vrchol i z naší komponenty.
Na pozici i
však po zašifrování libovolnou z mřížek vždy přejdou pouze znaky
z pozic spojených s i hranou a ty jsou v téže komponentě a mají
tedy stejnou hodnotu.
Vidíme, že t se nezmění zašifrováním právě tehdy, když jsou
v každé komponentě souvislosti na všech pozicích stejné znaky.
Každá z komponent může mít přiřazen jeden z K znaků,
přičemž znaky můžeme komponentám
přiřazovat nezávisle, celkový počet možností je proto KP.
Algoritmus řešení úlohy je tedy jednoduchý. Na základě mřížek
(simulací šifrování)
sestavíme graf G a pomocí prohledávání do šířky nebo do hloubky
zjistíme počet jeho komponent souvislosti P. Potom stačí
umocnit K na P. Graf G má
4N2 vrcholů, přičemž každý jeho vrchol má stupeň nejvýše 4.
Celkový počet hran v grafu je tedy nejvýše 8N2. Časová složitost
prohledávání grafu a také
celková složitost algoritmu je proto O(N2). Paměťová složitost
je také O(N2).
program P_III_1;
const max=50; {maximalni rozmer mrizky}
type pole=array [1..max,1..max] of boolean;
var mrizka,pom:pole;
{pole s mrizkou: true - vyrez, false - papir}
hrany:array [1..max*max,1..4] of integer; {hrany grafu}
byl:array [1..max*max] of boolean;
{zda jsme jiz prohledli dany vrchol}
n,k:integer; {rozmer mrizky, pocet pismen abecedy}
vys:longint; {vysledek}
i,j:integer;
procedure nactimrizku;
{do pole "mrizka" nacte mrizku ze vstupu}
var i,j,pom:integer;
begin
for i:=1 to n do
for j:=1 to n do begin
read(pom);
if pom=0 then mrizka[i,j]:=false
else mrizka[i,j]:=true;
end;
end;
procedure otoc;
{pomoci pomocneho pole "pom" otoci pole "mrizka"
o 90 stupnu ve smeru hodinovych rucicek}
var i,j:integer;
begin
for i:=1 to n do
for j:=1 to n do pom[i,j]:=false;
for i:=1 to n do
for j:=1 to n do
if mrizka[i,j] then pom[j,n-i+1]:=true;
mrizka:=pom;
end;
procedure vytvorhranu(z,k:integer);
{do pole "hrany[z]" prida cislo "k" na prvni nulove (volne) misto}
var i:integer;
begin
i:=1;
while hrany[z,i] <> 0 do i:=i+1;
hrany[z,i]:=k;
end;
procedure pridejhrany;
var i,j,otoceni,pozice,kam:integer;
begin
{postupne simulujeme sifrovani - pro kazdou pozici
ve vstupnim textu zjistime, kam se zapise,
a pridame odpovidajici hranu do grafu}
pozice:=1; {pozice ve vstupnim textu}
for otoceni:=1 to 4 do begin
for i:=1 to n do
for j:=1 to n do
if mrizka[i,j] then begin {nasli jsme otvor}
kam:=(i-1)*n+j; {kam se zapise znak na aktualni pozici}
vytvorhranu(pozice,kam); {pridame hranu}
vytvorhranu(kam,pozice);
pozice:=pozice+1;
end;
otoc; {otoceni mrizky o 90 stupnu}
end;
end;
procedure prohledej(vrchol:integer);
{prohledavani grafu do hloubky, v poli "byl" znaci navstivene vrcholy}
var i:integer;
begin
if not byl[vrchol] then begin
byl[vrchol]:=true;
for i:=1 to 4 do
prohledej(hrany[vrchol,i]);
end;
end;
function urcivysledek:longint;
{pocita pocet komponent a urci celkovy vysledek}
var i:integer;
v:longint;
begin
v:=1; {vysledek pro nula komponent}
for i:=1 to n*n do byl[i]:=false;
for i:=1 to n*n do
if not byl[i] then begin
{dosud nenavstiveny vrchol - prohledame jeho
komponentu a vysledek vynasobime cislem "k"}
prohledej(i);
v:=v*k;
end;
urcivysledek:=v; {"v" je nyni rovno "k" na pocet komponent}
end;
begin
readln(n,k);
n:=n*2; {n je delka strany}
for i:=1 to n*n do {nulovani hran}
for j:=1 to 4 do
hrany[i,j]:=0;
{zpracovani prvni mrizky:}
nactimrizku;
pridejhrany;
{zpracovani druhe mrizky:}
nactimrizku;
pridejhrany;
{vypocet vysledku:}
vys:=urcivysledek;
writeln('Pocet textu, ktere se nezmeni, je ',vys,'.');
end.
P-III-2 Hra se zápalkami
Pozici hry, kdy na první hromádce zbývá x a na druhé y zápalek,
budeme značit (x,y). Hra tedy začíná v pozici (a,b) a končí
v okamžiku, kdy se poprvé dostane do stavu (x,y) pro nějaká x,
y taková, že x < p a y < p.
Tahem rozumíme dvojici čísel (t,u) z množiny M={(p,0), (q,0),
(0,p), (0,q)}. Vykonáme-li v pozici (x,y) tah (t,u), hra přejde
do pozice (x-t,y-u). V pozici (x,y) je přípustné provést tah
(t,u) právě tehdy, je-li t <= x a u<= y.
O pozici (x,y) řekneme, že je vyhraná, jestliže v ní existuje vítězná
herní strategie pro hráče, který je právě na tahu. V opačném případě
označujeme pozici jako prohranou.
Ve vyhrané pozici musí existovat alespoň jeden přípustný tah,
který hru převede do prohrané pozice (tento tah je pak součástí
vítězné herní strategie). Naopak, libovolný tah přípustný
v prohrané pozici musí vést do nějaké pozice vyhrané (ať táhne
soupeř jakkoliv, opět budeme mít k dispozici tah vedoucí
k výhře).
Nejprve dokážeme následující větu:
Věta
Pozice (x,y) je vyhraná právě tehdy,
když pozice (x
1,y
1) je
vyhraná, kde x
1 a y
1
jsou zbytky po dělení čísel x,y číslem p+q.
Důkaz
Důkaz provedeme matematickou indukcí podle hodnoty x+y.
Pro x+y < p+q tvrzení zřejmě platí (x1=x, y1=y).
Nechť tvrzení platí pro všechna x,y taková, že x+y < s, kde
s >= p+q. Nechť x,y jsou libovolná čísla taková, že x+y=s.
Potom:
- Je-li pozice (x1,y1) vyhraná,
pak nutně existuje tah (t,u)
z M takový, že pozice (x1-t,y1-u)
je prohraná (x1-t >= 0, y1-u >= 0).
Protože ale (x-t)+(y-u) < s, podle indukčního předpokladu
je také pozice (x-t,y-u) prohraná a tedy pozice (x,y) je vyhraná,
neboť hráč na tahu v ní může provést vítězný tah (t,u).
- Je-li pozice (x1,y1) prohraná,
sporem předpokládejme, že
pozice (x,y) je vyhraná. Pak první hráč může svým tahem přejít
k prohrané pozici. Bez újmy na obecnosti předpokládejme, že
vítězný tah je odečtení čísla p od čísla x (další 3 možnosti lze
prošetřit analogicky). Pak pozice (x-p,y) je prohraná.
Označíme-li x2 zbytek po dělení čísla x-p číslem p+q, podle
indukčního předpokladu je pozice (x2,y1)
prohraná. Je-li
x1 >= p,
je (x2,y1)=(x1-p,y1),
je-li x1 < p,
je (x2,y1)=(x1+q,y1).
V obou případech dostáváme spor, neboť zřejmě nemohou být
současně prohrané pozice (x
1,y
1) a
(x
1-p,y
1) ani (x
1,y
1)
a (x
1+q,y
1).
Dále se budeme zabývat analýzou pozice (x,y) v případě, že x < p+q
a y < p+q. Nejprve spočítáme paritu počtu tahů zbývajících do konce
hry v pozici (x,0), kde 0 <= x < p+q:
- Je-li x < q, hráči pouze mohou odečítat hodnotu p a tedy
provedou právě [x/p] tahů.
- Je-li x >= q, hráči mohou buď provést právě jeden tah
(v případě, že odečtou číslo q), nebo provedou právě [x/p] tahů
(v případě, že v prvním tahu odečtou číslo p, v dalších tazích
mohou odečítat pouze číslo p a nikdy nemohou odečíst číslo q).
Tedy platí:
- Je-li [x/p] liché, hra má vždy lichý počet tahů.
- Je-li [x/p] sudé a x < q, hra má vždy sudý počet tahů.
- Je-li [x/p] sudé a x >= q, hra může mít sudý nebo lichý počet
tahů, přičemž o tom rozhoduje první tah.
Nyní mějme obecnou počáteční pozici (a,b). Protože začínající
hráč vyhrává hru právě tehdy, když celkový počet tahů je lichý,
snadno ukážeme, že platí:
Věta
Pozice (a,b) je pro a < p+q, b < p+q prohraná právě tehdy, když
nastane jedna z následujících dvou možností:
- [ a/p ], [ b/p ] jsou obě lichá čísla
- [ a/p ], [ b/p ] jsou obě sudá čísla
[ a/q ] +[ b/q ] je sudé
Důkaz
Rozebereme 9 možností podle toho, jakou z podmínek A, B, C splňují
čísla a, b. Nesplňuje-li žádné z čísel a, b podmínku C, výsledek
nezáleží na hře hráčů a zřejmě sudý počet tahů nastane právě
tehdy, když buď obě splňují A, nebo obě splňují B. Splňuje-li
právě jedno z čísel a, b podmínku C, první hráč toto číslo může
vhodně snížit tak, aby vyhrál, neboť počet tahů druhým číslem je
pevně určen. Konečně, splňují-li obě čísla podmínku C, vyhrává
druhý hráč, neboť po libovolném tahu prvního hráče může druhý
hráč s nepoužitým číslem provést stejnou operaci a tím dosáhnout
sudého počtu tahů. Tedy pozice (a,b) je prohraná, splňují-li
čísla a, b stejnou podmínku A, B nebo C, což dává ihned dokazované
tvrzení.
Z dokázaných vět přímo plyne:
Startegie
Pro libovolná a, b celá nezáporná je pozice (a,b) prohraná, právě
tehdy, když nastává právě jedna z možností
-
- [ a1/p], [ b1/p] jsou obě lichá
- [ a1/p], [ b1/p] jsou obě sudá a
[ a1/q]+[ b1/q] je sudé
kde a
1, b
1 jsou zbytky
po dělení čísel a,b číslem p+q.
P-III-3 Markovovy algoritmy
Úloha a
1. b
01 -> 1b
0
2. b
0 -> }
3. {11 -> 1{
4. {1 -> {
5. {} -> |}1
6. 1| -> |1
7. |} ->
._
8. | -> {
9. 11 -> {1b
0
10. 1 -> 1
Jestliže vstupní slovo obsahuje jedinou jedničku reprezentující
hodnotu nula, bude se provádět opakovaně formule 10 a dojde
k zacyklení výpočtu (algoritmus je pro nulu nepřípustný).
Je-li na vstupu kladné číslo N (zapsané jako N+1 jedniček),
vykoná se nejprve formule 9, kterou se na začátek slova umístí
závorka { a odstraní se jedna nadbytečná jednička používaná
ve zvoleném kódování čísel. Opakovaným prováděním formule 1 se pak
přemístí pomocný symbol b
0 na pravý okraj slova, kde se formulí
2 přemění na závorku }. Po použití trojice pravidel 9, 1, 2 bude
tedy vstupní slovo převedeno na tvar {11111111} (N jedniček
v závorkách).
Následně se vždy opakováním formule 3 vydělí číslo dvěma, pomocí
pravidla 4 se případně odstraní zbývající lichá jednička
a použitím 5 se přičte jedna jednička do výsledku, který je
vytvářen na pravém okraji slova za znakem }. Formule 6 a 8 pak
zajistí obnovení situace před dalším dělením. Po dosažení
nulového výsledku dělení se uplatní pravidlo 7, které smaže
zbývající pomocné symboly a výpočet ukončí.
Popsaný algoritmus je založen na skutečnosti, že dolní celá část
dvojkového logaritmu čísla N udává, kolikrát můžeme číslo
opakovaně celočíselně vydělit dvěma, než dostaneme nulový
výsledek. Formule 6 se uplatní i v případě nulového podílu
a připíše jednu 1 k výsledku - ve výsledku se proto objeví vždy
o jednu 1 více, než kolik je správná hodnota dvojkového
logaritmu. To však přesně odpovídá zvolenému kódování čísel.
Přípravná fáze výpočtu uvedeného algoritmu (použití formulí 9,
1 a 2) se provádí pouze jednou a představuje pro vstupní hodnotu
N provedení O(N) kroků výpočtu. Poté (formule
3-8) se (log2N)-krát opakuje dělení čísla dvěma.
Při prvním dělení se
provede maximálně N+4 kroků ( (N/2)-krát pravidlo 3, (N/2)-krát pravidlo
6, ostatní se vykonají pouze jednou), při druhém N/2+4 kroků
výpočtu, při třetím N/4+4, atd. Celková doba výpočtu navrženého
Markovova algoritmu vyjádřená počtem vykonaných kroků je
tedy shora omezena
O(N) + N + N/2 + N/4 + N/8 + ... + 1 + 4 log2 N.
Součet geometrické řady 1/2 + 1/4 + 1/8 + ... se blíží hodnotě
1, celkem se proto vykoná O(O(N)+N+log N)=O(N) kroků výpočtu.
Úloha b
1. X01 -> X01
2. X00 -> X00
3. X0 ->
._
4. X1 -> B
5. A0 -> A
6. A1 -> B
7. B0 -> C
8. B1 -> A
9. C0 -> B
10. C1 -> C
11. A ->
._
12. B -> B
13. C -> C
14. _ -> X
Formule 14 nejprve umístí na začátek vstupního slova pomocný
symbol X. Podle začátku zadaného slova se pak provede jedna
z formulí 1-4. Binární zápis čísla nemůže začínat nulou a přitom
obsahovat více než jednu cifru - v takovém případě se uplatní
pravidlo 1 nebo 2 a dojde k zacyklení výpočtu nad nepřípustným
vstupem. Obsahuje-li vstupní slovo jedinou nulu, zajistí pravidlo 3
ukončení výpočtu - algoritmus je přípustný, neboť nula je beze
zbytku dělitelná třemi. Konečně začíná-li binární zápis čísla
cifrou 1, je tato cifra nahrazena pomocným symbolem B a výpočet
pokračuje v další části schématu.
Formule 5-10 provádějí jednoduchou analýzu zadaného řetězce,
který obsahuje kladné celé číslo korektně zapsané ve dvojkové
soustavě. Číslo zpracováváme zleva doprava cifru po cifře
a sledujeme, jaký zbytek po dělení třemi dává číslo představované
již zpracovanými dvojkovými číslicemi. Podle hodnoty tohoto
zbytku měníme pomocný symbol na A, B nebo C (A pro zbytek 0,
B pro zbytek 1, C pro zbytek 2). Formule 4 odebrala z dvojkového
zápisu čísla vedoucí jedničku a pomocný symbol nastavila na B,
neboť číslo jedna dává po dělení třemi zbytek 1.
Máme-li již přečtenu z levé strany vstupního řetězce skupinu
dvojkových cifer představující nějaké číslo v, můžeme rozlišit
tři případy podle zbytku po dělení čísla v třemi:
- v je beze zbytku dělitelné třemi (stav A)
- přidáme-li k jeho dvojkovému zápisu cifru 0, dostaneme hodnotu
2v, která je rovněž dělitelná třemi (formule 5)
- přidáme-li k jeho dvojkovému zápisu cifru 1, dostaneme hodnotu
2v+1, která dává při dělení třemi zbytek 1 (formule 6)
- v dává po dělení třemi zbytek 1, je tedy tvaru v=3k+1 (stav B)
- přidáme-li k jeho dvojkovému zápisu cifru 0, dostaneme hodnotu
2v=6k+2, která dává při dělení třemi zbytek 2 (formule 7)
- přidáme-li k jeho dvojkovému zápisu cifru 1, dostaneme hodnotu
2v+1=6k+3, která je beze zbytku dělitelná třemi (formule 8)
- v dává po dělení třemi zbytek 2, je tedy tvaru v=3k+2 (stav C)
- přidáme-li k jeho dvojkovému zápisu cifru 0, dostaneme hodnotu
2v=6k+4, která dává při dělení třemi zbytek 1 (formule 9)
- přidáme-li k jeho dvojkovému zápisu cifru 1, dostaneme hodnotu
2v+1=6k+5, která dává při dělení třemi zbytek 2 (formule 10)
Po zpracování celého vstupního slova určuje poslední pomocný
symbol, jaký je výsledný zbytek po celočíselném dělení zadaného
čísla třemi. Je-li výsledným symbolem A, zadané číslo bylo
dělitelné třemi a formule 11 proto výpočet úspěšně ukončí.
V případě symbolů B a C se jednalo o dvojkový zápis čísla, které
nebylo dělitelné třemi - pomocí pravidla 12 nebo 13 se tedy
zajistí zacyklení výpočtu nad nepřípustným vstupním slovem.
Celý výpočet má zjevně lineární časovou složitost vzhledem
k délce zadaného vstupního slova, pro přípustné vstupní hodnoty
je počet vykonaných kroků přímo úměrný počtu číslic zkoumaného
čísla.