Matematická olympiáda – kategorie P

Řešení úloh domácí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.

  1. 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.

    1. 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).

    2. 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í.

  2. Text původní zprávy z dané úlohy tedy je "KRYPTOGRAFIE".

  3. 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.

  4. 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:

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 b1 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 b1 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)xb3b2y->b2yxb3(x,y prvky T)
(2)xb1yb3->yb3xb1(x,y prvky T)
(3)b3->b1
(4)b1xb1->xb1(x prvek T)
(5)b1b1->b1
(6)b1x->b2xb1(x prvek T)
(7)b2x->xxb3(x prvek T)
(8)b1->._
(9)_->b1
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.