Řešení úloh školního kola 48. ročníku
P-I-1 Kódovací mřížka
Jde o úlohu na procvičování indexování ve dvojrozměrném poli. Při
sestavování algoritmu dáme přednost užití těch datových
a řídicích struktur, které vedou již při první kolizi k odhalení
faktu, že zadaná vstupní data nereprezentují kódovací mřížku.
Mřížku lze reprezentovat jako čtvercovou boolskou matici o 2N
řádcích a 2N sloupcích, jejíž prvky inicializujeme na hodnoty
false. Vlastní jádro algoritmu je možno zapsat jako jeden cyklus
while, který končí buď v okamžiku, kdy jsme po přečtení dalšího
znaku představujícího výřez zjistili kolizi nebo v okamžiku, kdy
byla načtena všechna vstupní data.
V každé iteraci po přečtení znaku 1 (výřez) zjišťujeme, zda tento
výřez nekoliduje na čtyřech odpovídajících místech s některým z
předchozích výřezů. Nekoliduje-li, označíme prvky matice pod
čtyřmi možnými pozicemi načteného výřezu hodnotou true.
Po ukončení načítání všech vstupních dat musí být přečeno přesně
N2 výřezů a hodnota proměnné ANO musí
být rovna true (t.j.
nedošlo k žádné kolizi), aby odpověď mohla být ANO, jinak je
výsledná odpověď NE.
program MRIZKA;
{Program pro zjištění správnosti kódovací mřížky}
const maxNN = 40; {maximální kódovací mřížka}
var KM=[array 1..maxNN,1..maxNN] of boolean; {kódovací mřížka}
i,j:integer; {indexy čteného znaku v kódovací mřížce}
i1,j1:integer; {pomocné indexy}
N2:integer; {počet řádků a sloupců v kódovací mřížce}
zn:integer; {aktuální čtený znak}
POCONE:integer; {registr počtu výřezů}
ANO:boolean; {indikátor vzniklé kolize}
T:Text; {vstupní a výstupní soubor}
begin
assign(T,'MRIZKA.IN');
reset(T);
readln(T,N); {velikost kódovací mřížky}
N2:=2*N;
for i:=1 to N2 do
for j:=1 to N2 do KM[i,j]:=False; {žádná pozice nebyla načtena}
ANO:=True;i:=1;j:=1;POCONE:=0; {počáteční nastavení}
{pokud nebyla odhalena kolize a}
{nejsou otestována všechna vstupní data}
while (ANO) and (i<=N2) do
begin read(T,zn); {přecti další znak ze vstupu}
if zn=1 then {pokud jde o výřez}
begin POCONE:=POCONE+1; {zaregistruj jej}
i1:=N2-i+1;
j1:=N2-j+1; {pro 4 pozice mřížky}
if KM[i,j] then {pokud nastala kolize}
ANO:=False {oznam, ji}
else KM[i,j]:=True; {jinak registruj výřez}
if KM[j,i1] then
ANO:=False
else KM[j,i1]:=True;
if KM[i1,j1] then
ANO:=False
else KM[i1,j1]:=True;
if KM[j1,i] then
ANO:=False
else KM[j1,i]:=True;
end;
{nastav indexy pro vstup dalšího znaku}
if (j=N2) then begin j:=1;i:=i+1 end
else j:=j+1
end;
close(T);
{podle zjištěných skutečností tiskni výslednou zprávu}
assign(T,'MRIZKA.OUT');
rewite(T);
if (not ANO) or (POCONE<(N*N)) then writeln (T,'NE')
else writeln (T,'ANO');
close(T)
end.
Poznámka
V jiném typu algoritmu stačí deklarovat čtvercovou boolskou
matici pouze o N řádcích a N sloupcích, ve které je možno
pamatovat přečtené výřezy pouze v jednom prvku matice. Pak je
ovšem nutno modifikovat při zjišťování možných kolizí řádkové
i sloupcové indexy deklarované matice pro registraci výřezu při
každém přečtení výřezu.
P-I-2 Tajemný kryptogram
Jedná se o variantu skutečně používaného šifrovacího systému, který je kombinací substituční a transpoziční šifry - tzv. kombinovaná šifra.
Terminologická poznámka - čistým textem, popř. otevřeným textem se označuje
vstupní nezašifrovaný text.
- Postup při zašifrování
Nejprve je provedena substituce podle tabulky č.1,
poté transpozice podle tabulky č.2. Mezery v čistém textu
jsou vynechány, pro jednoduchý
program a determenistické řešení přepisu podle tabulky č.2
je potřeba několik omezení krajních případů (příliš krátký
vstupní text ap.) - viz přiložený zdrojový program.
- Jednotlivé znaky čistého textu jsou přepsány do dvojic písmen podle tabulky č.1 tak, že nejdříve je uváděn řádek, poté sloupec. Příklad:
Q je přepsáno na GF, 5 na XG, Í na DX. Takto získané dvojice písmen zapisujeme do posloupnosti, kterou označujeme (např. i v přiloženém programu) jako mezišifru. Postup přepisování písmen (jedno písmeno substituujeme dvojicí písmen označující řádek a sloupec pozice v tabulce) označujeme jako kryptografický algoritmus, sama tabulka je pak kryptografickým klíčem (specifickým parametrem pro práci algoritmu).
- Mezišifru postupně zapisujeme do řádků tabulky č.2, jejíž záhlaví tvoří další klíč - klíč transpoziční šifry. Po zaplnění prvního řádku pokračujeme na druhém řádku a takto postupujeme tak dlouho dokud nezapíšeme celou mezišifru. Pokud celý poslední řádek nevyplníme, necháme na místech mezery.
V této části úlohy je potřeba si všimnout důležitého požadavku ze zadání - že se záhlaví skládá z různých písmen abecedy. Abecední pořadí těchto písmen totiž určuje klíč pro transpoziční šifru - pořadí, ve kterém vypisujeme obsah jednotlivých sloupců tabulky a vytváříme tak výsledný
zašifrovaný text. U tabulky uvedené v zadání domácího kola MO je to tedy
nejprve sloupec označený E, poté sloupec označený H atd., až jako poslední
vypisujeme písmena ze sloupce označeného Y.
Postup při dešifrování je zřejmý z popisu zašifrování.
- Text původní zprávy z dané úlohy tedy je "KRYPTOGRAFIE".
- Zašifrování způsobuje nárůst zprávy v první části (substituce podle tabulky č.1) - faktor nárůstu je zde 2, případně lze započítat mezery uvedené při přepisu mezišifry ve sloupcích na výsledný zašifrovaný text - tento nárůst bude o (P-1)M, kde P je počet sloupců tabulky (délka klíče pro transpoziční šifru) a M je počet znaků/mezer použitých k oddělení výpisů jednotlivých sloupců.
Jako správná odpověď na tuto otázku ovšem plně dostačuje faktor nárůstu pro substituční šifru - 2.
- Program pro zašifrování textu v TurboPascalu je přiložen.
Program Kryptografie;
{Ze vstupniho souboru KRYPT.IN se nacte otevreny (nezakodovany)
text a zahlavi Tabulky 2. Pocet znaku v otevrenem textu je
alespon dvojnasobkem poctu znaku v zahlavi Tab. 2,
otevreny text neni delsi nez 127 znaku
(aby se mezisifra dala zapsat do stringu).
Jak otevreny text, tak i zahlavi 2 na vstupu konci znakem '#'.
Program zasifruje otevreny text s pomoci interne integrovane
kodovaci Tabulky 1 a zahlavi Tabulky 2 ze vstupu a tuto sifru
vypise do vystupniho souboru KRYPT.OUT'.}
const Tab1: array[1..7,1..7] of char = {Tabulka 1}
(('Z','3','E','N','V','Ó','A'), {diakritika}
('Y','É','Ě','Č','Ď','Š','Í'), {v Latin 2}
('D','H','8','2','O','Ř','0'),
('J','P','Q','X','7','Ť','G'),
('W','R','K','F','Á','Ú','1'),
('I','S','U','M','4','Ž','T'),
('6','C','9','5','B','Ů','L'));
Z1: string[7] = 'ADFGVMX'; {zahlavi Tab. 1}
var Z2: string; {zahlavi Tab. 2}
Min: byte; {pomocny index do zahlavi 2 pro hledani minima}
MS: string; {mezi-sifra}
OT: string; {otevreny text}
Nasel: boolean; {True: znak byl nalezen v Tab. 1}
Vystup: byte; {pocet vypsanych znaku na vystup;}
{musi byt roven delce mezi-sifry MS}
T: text; {vstupni a vystupni soubor}
I, J, K: byte; {ridici promenne cyklu}
Mezera: char; {pomocna promenna}
{pro zapis mezery do souboru}
begin
assign(T, 'Krypt.in'); {vstupni soubor}
reset(T);
OT := ''; {nic nenacteno}
repeat
readln(T, MS);
{nacteni radku ze vstupniho souboru;}
{MS pouzito jako pomocny string,}
{dale v programu ma vyznam mezi-sifry}
OT := concat(OT, MS); {pridani radku k otevrenemu textu}
until MS[length(MS)] = '#'; {posledni znak je '#'}
delete(OT, length(OT), 1); {smazani znaku '#' z OT}
Z2 := ''; {zadna cast zahlavi nebyla nactena}
repeat
readln(T, MS); {nacteni radku ze vstupniho souboru}
Z2 := concat(Z2, MS); {pridani radku k zahlavi Tab. 2}
until MS[length(MS)] = '#'; {posledni znak je '#'}
delete(Z2, length(Z2), 1); {smazani znaku '#' ze Z2}
close(T); {zavreni vstupniho souboru}
MS := ''; {zatim zadna mezi-sifra}
I := 1; {kodovat se bude 1. znak otevreneho textu}
Nasel := True; {nenalezen neznamy znak v OT}
while (I <= length(OT)) and (Nasel) do
{neni vse zakodovano}
{a zatim byly vsechny znaky zakodovatelne,}
{nachazely se v Tab. 1}
begin
J := 1; {prohledat 1. radek Tab. 1}
Nasel := False; {znak nebyl nalezen v Tab. 1}
while (J < 8) and (not Nasel) do
{dokud je radek platny ( J < 8)}
{a hledany znak OT[I] nebyl nalezen v Tab. 1}
begin
K := 1; {prohledavat J-ty radek od 1. sloupce}
while (Tab1[J,K] <> OT[I]) and (K < 8) do K := K + 1;
if K < 8 then {na pozici Tab1[J,K] je hledany znak}
begin
Nasel := True; {znak nalezen v Tab. 1}
MS := concat(MS, Z1[J], Z1[K]); {pridat do mezi-sifry}
end
else J := J + 1; {projit dalsi radek Tab. 1}
end;
I := I + 1; {kodovat dalsi znak z OT}
end;
assign(T, 'Krypt.out'); {vystupni soubor}
rewrite(T);
Mezera := ' '; {mezera pro oddelovani}
{'sloupcu Tabulky 2' na vystupu}
if Nasel then {vsechny znaky z OT byly nalezeny v Tab. 1}
repeat
Min := 1;
{'Min' je index na 'nejmensi' znak v zahlavi 2; pokud byl
jiz tento znak pouzit, je na jeho pozici zapsan znak
#200, ten je urcite 'vetsi' jak vsechna pismena
(anglicke abecedy - ta se dobre abecedne tridi)}
while Z2[Min] = #200 do Min := Min + 1;
{preskocit uz pouzite pozice; v Z2 existuje jeste takovy
znak, ktery nebyl pouzit}
for I := (Min+1) to length(Z2) do
{hledat 'mensi' znak jak Z2[min]}
if Z2[I] < Z2[Min] then Min := I;
{'mensi' znak na I-te pozici}
Z2[Min] := #200;
{znak Z2[Min] byl jiz pouzit - pro dalsi prohledavani}
while Min <= length(MS) do
{Min je platny index do retezce mezi-sifry}
begin
write(T, MS[Min]); {vypsat znak do vystupniho souboru}
Vystup := Vystup + 1; {dalsi znak na vystup}
Min := Min + length(Z2);
{dalsi 'kandidatska' pozice do mezi-sifry}
end;
write(T, Mezera);
{oddelovat 'sloupce Tab. 2' v sifre mezerou}
until Vystup = length(MS)
{vsechny znaky z MS jsou na vystupu}
else begin
MS :='Neznamy znak; nelze zakodovat.';
{Nasel = False, tzn. ze v OT byl nezasifrovatelny znak,
MS pouzit opet jako pomocny string}
write(T, MS);
end;
close(T); {zavreni vystupniho souboru}
end.
P-I-3 Hra se zápalkami
Protože se v každém tahu celkový počet zápalek zmenší, hra je
zřejmě vždy konečná a tedy existuje vítězná strategie pro jednoho
z hráčů.
Předpokládejme, že M, podmnožina N03,
je množina trojic všech
čísel (a,b,c), která splňuje:
- (0,0,0) je prvkem M
- Pro všechny a,b,c prvky N0 a
pro všechny A,B,C prvky N0 (A < a, B < b, C < c) platí:
Je-li (a,b,c) prvkem M, potom (A,b,c),(a,B,c),(a,b,C) není prvkem M.
- Pro všechny a,b,c prvky N0 a
pro všechny A,B,C prvky N0 (A < a, B < b, C < c) platí:
Není-li (a,b,c) prvkem M, potom alespoň jedna z trojic
(A,b,c),(a,B,c),(a,b,C) je prvkem M.
Ze zadání a z definice množiny M snadno nahlédneme, že M je
množina právě těch trojic čísel (a,b,c), pro které existuje
vítězná strategie pro druhého hráče. Důkaz provedeme indukcí
vzhledem k a+b+c.
Na základě tohoto tvrzení by bylo možno snadno zapsat rekurzivní
algoritmus, který by řešil danou úlohu. Ten by však měl
nevyhovující exponenciální časovou a paměťovou složitost.
Ukážeme, že výše uvedneým podmínkám vyhovuje množina
M={ (a,b,c) | a XOR b XOR c = 0}.
První podmínka je splněna zřejmě. Druhá podmínka je splněna
také, neboť kdyby například (a,b,c) bylo prvkem M i (A,b,c) bylo prvkem M,
bylo by i a XOR b XOR c = A XOR b XOR c
= 0, odkud ale a = b XOR c = A, což by byl spor.
Zbývá tedy ověřit poslední podmínku. Zapišme čísla a,b,c
ve dvojkové soustavě:
a=a020+a121+...
b=b020+b121+...
c=c020+c121+...
(ai,bi,ci jsou 0 a 1).
Protože čísla a,b,c jsou konečná, existuje číslo m takové, že
pro libovolné i > m je ai = bi =
ci = 0. Protože ale a
XOR b XOR c <> 0, musí existovat index i
takový, že číslo
ai+bi+ci je liché.
Nechť k je tedy
největší takový index.
Pak číslo ak+bk+ck je liché, tedy
alespoň jedno z čísel ak,bk,ck
je liché. Nechť je to
například číslo ak.
Pro libovolné i, které je prvkem N0, označme Ai =
(bi + ci) mod 2. Dále položme
A=A020+A121+...
Zřejmě je A = b XOR c,
tedy A XOR b XOR c = 0, tedy (A,b,c) je prkvem M. Protože
pro i > k je zřejmě Ai = ai a
dále je ak = 1 > 0 > Ak, je A < a.
Tedy také poslední podmínka je splněna.
Nyní již snadno sestrojíme algoritmus s konstantní časovou
i paměťovou složitostí.
Označme x = b XOR c, y = a XOR c, z = a XOR b.
Zřejmě je x XOR b XOR c = a XOR y XOR c
= a XOR b XOR z = 0, tedy (x,b,c),(a,y,c),(a,b,z) jsou prvky M.
Je-li x < a , pak tah (x,b,c) vede k vítězné strategii pro
prvního hráče. Je-li y < b, pak tah (a,y,c) vede k vítězné
strategii pro prvního hráče. Je-li z < c, pak tah (a,b,z)
vede k vítězné strategii pro prvního hráče.
Je-li x >= a , y >= b i z >= c, pak v dané pozici
je vítězná strategie pro druhého hráče, neboť kdyby
(a,b,c) nebylo prkvem M, pak by podle posledního bodu
existovala čísla
A,B,C (prvky N0, A < a, B < b,
C < c ) taková, že A XOR b XOR c = 0 nebo
a XOR B XOR c = 0 nebo
a XOR b XOR C = 0. Tyto podmínky jsou ale ekvivalentní
s A= b XOR c = x, B = a XOR c = y, C= a XOR b = z,
tedy x < a nebo y < b nebo z < c, což by byl spor.
Úloha je vyřešena.
program hra;
var
t,u:text; {Vstupni a vystupni soubor }
n:byte; {Pocet zadani }
a,b,c:byte; {Vstupni pocty zapalek }
x,y,z,i:byte; {Pomocne promenne }
begin
assign(t,'input.txt');
reset(t); {Inicializace vstupniho souboru}
assign(u,'output.txt');
rewrite(u); {Inicializace vystupniho souboru}
readln(t,n); {Nacteni poctu zadani}
for i:=1 to n do begin {Vyres jedno zadani}
readln(t,a,b,c); {Nacti vstupni pocty zapalek}
x:=b xor c; {Proved pomocny vypocet}
y:=a xor c;
z:=a xor b;
if x < a then writeln(u,x,' ',b,' ',c) else begin
if y < b then writeln(u,a,' ',y,' ',c) else begin
if z < c then writeln(u,a,' ',b,' ',z)
else writeln(u,'NE')
end
end;
end;
close(t);
close(u);
end.
P-I-4 Markovovy normální algoritmy
Úloha a
Jde o snadné cvičení dokumentující pojem přípustnost a
nepřípustnost algoritmu. Algoritmus je nepřípustný pro nějaké
slovo P právě tehdy, když po aplikaci některého pravidla ze
schématu algoritmu bude jistě možno aplikovat v dalším kroku
činnosti algoritmu nějaké pravidlo z daného schématu.
Nejjednodušším případem, který tuto podmínku zajistí, je použít
takové pravidlo, které ponechá slovo v původním stavu (viz
příklad 1 v zadání).
Existence znaku * ve slově je příznakem toho, že ve slově je
zapsán vektor a nikoliv číslo. Stačí tedy zjištěný znak *
ponechat beze změny. Jinak můžeme při existenci více než jednoho
znaku 1 ve slově dvojici 11 přepsat na 1, tj. odečteme jednotku.
Jestliže ve slově zůstane jediný znak 1, algoritmus končí,
poněvadž již nelze aplikovat žádné pravidlo ze schématu a toto
slovo je správným výsledkem.
Řešení
* -> *
11 -> 1
Úloha b
Studujme nejdříve činnost algoritmu podle schématu
v příkladu 4 ze zadání. Všimněte si, že vždy nejdříve předznačí
symbolem b
1 znak, který budeme v následujících krocích
přesouvat na správné místo i s jeho předznačením. Po zjištění, že
už není co přesouvat, všechny symboly b
1 ze zpracovávaného
slova vymaže. Tento postup můžeme využít i při řešení naší úlohy.
Hledaný algoritmus nejdříve předznačí symbolem b2 všechny
znaky (pravidla 9,6), které se musí napřed zdvojit (pravidlo 7)
a zdvojující znak označený znakem b3 přesunout do druhé
poloviny výsledku. Slovo bude v průběhu práce algoritmu zakončeno
znakem b1. Přesun provedeme ve třech krocích.
V prvním kroku se přesune druhý ze dvojice znaků vzniklý
zdvojením i s jeho označením b3 (pravidlo 1) podobně jako u
příkladu 4. Po skončení prvního kroku máme slovo sice zdvojené,
ale v pravé polovině slova jsou všechny znaky označeny symbolem
b3 a navíc jsou zrcadlově otočeny.
Ve druhém a třetím kroku pracujeme pouze s pravou polovinou
slova. Ve druhém kroku otočíme pořadí znaků v pravé polovině
slova (pravidla 3 a 2) a označení b3 změníme na b1.
V posledním kroku vymažeme z výsledku všechna předznačení b1
(pravidlo 4). Dva po sobě jdoucí symboly b1b1 (první byl zapsán
na konec slova v úvodní části algoritmu) indikují konec práce
algoritmu nad neprázdným slovem (pravidlo 5). Činnost algoritmu
končí závěrečným použitím koncového pravidla číslo 8.
Řešení
(1)xb
3b
2y->b
2yxb
3(x,y prvky T)
(2)xb
1yb
3->yb
3xb
1(x,y prvky T)
(3)b
3->b
1
(4)b
1xb
1->xb
1(x prvek T)
(5)b
1b
1->b
1
(6)b
1x->b
2xb
1(x prvek T)
(7)b
2x->xxb
3(x prvek T)
(8)b
1->
._
(9)_->b
1
Ověřte činnost algoritmu na příkladech zdvojení některých slov
(např. abc, ab, a) i na prázdém slově _, pro které musí
být algoritmus rovněž přípustný.
Dbejte, aby výsledné schéma obsahovalo pravidla ve správném
pořadí, t.j. aby algoritmus nezačal dělat něco jiného, než je
uvedeno v jeho popisu.