Matematická olympiáda – kategorie P

Řešení úloh domácího kola 46. ročníku

P-I-1

Autor úlohy vytvořil pro tuto úlohu vlastní webovou stránku (ke spuštění hry je potřebný WWW-prohlížeč s Javou).

Řešení úlohy

Nejprve se pokusíme odpovědět na otázku, kdy úloha nemá řešení. Po získání určitých praktických zkušeností s hrou zjistíme, že každou počáteční situaci S dokážeme převést na situaci K=1,2,...,13,14,15,0 nebo N=1,2,...,13,15,14,0, kde 0 představuje prázdné políčko. Po dalších zkušenostech získáme přesvědčení (podpořené i prvním příkladem v zadání úlohy), že situace N je neřešitelná. To ale znamená také neřešitelnost počáteční situace S. Jinak bychom N vyřešili převodem na S ("zpětným chodem" - zopakováním převodu S na N v opačném pořadí) a následným převodem S na K. Jestliže tedy budeme mít algoritmus, který libovolnou počáteční situaci S převede buď na K nebo na N, umíme rozhodnout o řešitelnosti S: stačí se podívat, zda jsme skončili v K nebo v N.

Řešitelné a neřešitelné situace se dokonce dají matematicky charakterizovat. Tato charakterizace nám poskytne důkaz neřešitelnosti N a tím dá úvahám předcházejícího odstavce pevný základ.

Zavedeme nejprve pojem počet inverzí dané situace S: Vypíšeme si čísla kamínků S za sebou, ale vynecháme 0 (prázdné políčko). Pro situaci A uvedenou v zadání bychom dostali posloupnost 7,12,9,3,14,15,10,1,8,13,5,11,6,2,4. Inverze je taková dvojice (i,j) členů této posloupnosti, že i předchází v posloupnosti j a přitom i > j. Např. 12 a 9 tvoří inverzi v posloupnosti A, která má celkem 6+10+7+2+9+9+6+0+4+5+2+3+2+0+0=65 inverzí. Dalším číslem, které nás bude zajímat, je číslo řádku (1 až 4), ve kterém se nachází prázdné políčko (pro A je to 2). Charakteristikou C(A) situace A nazveme součet těchto dvou čísel (počtu inverzí a čísla řádku prázdného políčka). Všimněte si, že C(A)=65+2=67, C(K)=0+4=4 a C(N)=1+4=5. Co se stane s charakteristikou, když přejdeme povoleným krokem ze situace S do S'? Rozlišíme dva případy:

  1. krok vodorovným směrem (doleva, doprava): ani jeden ze sčítanců se nezmění, tedy C(S)=C(S').
  2. krok svislým směrem (nahoru, dolů): číslo řádku se změní o 1. Počet inverzí se změní o 1 nebo o 3 (dokažte!).
Celkově tedy C(S) patří do stejné zbytkové třídy při dělení dvěma jako C(S'). Jinými slovy řečeno, parita charakteristiky se povolenými kroky nemění.

Jestliže má počáteční situace lichou charakteristiku, určitě se nedá převést na koncovou situaci K a proto je neřešitelná. Neřešitelná je tedy i situace N, stejně jako všechny situace, které se na ni dají převést posloupností povolených kroků.

Algoritmus

Uvedeme nyní algoritmus (a program), který libovolnou počáteční situaci převede buď na K, nebo na N (přesněji, na neřešitelnou situaci N'=(1,2,3,4,5,6,7,8,9,10,11,15,13,14,12,0) s charakteristikou C(N')=5+4=9). Myšlenka algoritmu je jednoduchá: postupně dostaneme na své místo kamínky číslo 1, 2, 3, 4, 5, 6, 7, 8, 9, 13, 10, 14, 11 a 0 (prázdné políčko na pozici 16). Pokud je po skončení kamínek 15 na svém místě, je i 12 v pořádku a máme K, jinak jsme dospěli k N'. Pro každý kamínek (např. k), který chceme uvedeným způsobem dostat na místo, definujeme cyklus - cyklickou posloupnost sousedních pozic obsahující:
Kamínky budeme přesouvat po tomto cyklu, dokud se k nedostane na své místo (toto ještě upřesníme později). Můžeme dokonce předepsat, kde má skončit prázdné políčko. Procedura Cykluj(Ktery,Kam,nP) v programu posouvá kamínky po cyklu (určeném kamínkem Ktery) tak, až se Ktery dostane na pozici Kam a pozice nP (nech Prázdnou) zůstane prázdná. Cykly zásadně obcházejí pozice, kterým už algoritmus přidělil správný kamínek. Jednotlivé cykly vypadají takto (uvádíme je ve směru putování prázdného políčka):
Ktery Kam nP cyklus délka
1 1 2 1,2,3,4,8,12,16,15,11,7,6,10,14,13,9,5,1 16
2 2 3 2,3,7,8,12,16,15,11,10,14,13,9,5,6,2 14
3 3 8 3,4,8,12,16,15,11,10,14,13,9,5,6,7,3 14
4 8 12 5,6,7,8,12,16,15,11,10,14,13,9,5 12
5 5 6 5,6,7,8,12,16,15,11,10,14,13,9,5 12
6 6 7 6,7,11,12,16,15,14,13,9,10,6 10
7 7 12 7,8,12,16,15,14,13,9,10,11,7 10
8 12 16 9,10,11,12,16,15,14,13,9 8
9 9 14 9,13,14,15,16,12,11,10,9 8
13 14 15 10,11,12,16,15,14,10 6
10 10 15 10,14,15,16,12,11,10 6
14 15 16 11,15,16,12,11 4
11 11 16 11,12,16,15,11 4
Tyto cykly jsou zakódovány v proměnné Cykly.

Musíme ještě vysvětlit dva problematické body. Poté, co jsme dostali kamínek 1 na pozici 1 (a pozice 2 je prázdná), může se stát, že kamínek 2 je na pozici 4, tedy mimo druhý cyklus. To vyřešíme uplatněním kroků 3,4,8 (kamínek 2 se ocitne na pozici 3 a pozice 8 zůstane prázdná). Obdobný problém je s kamínkem 6.

Druhý problém se týká umístění "rohových" kamínků 4, 8, 13 a 14 - právě u nich je Ktery <> Kam v tabulce. Když už jsme umístili kamínky 1, 2 a 3, žádný cyklus obcházející pozice 1, 2 a 3 neprochází pozicí 4. Proto kamínek 4 neumisťujeme na pozici 4 přímo (pokud, samozřejmě, ještě na ní neleží), ale na pozici 8 a pozici 12 necháme prázdnou - viz cyklus pro kamínek 4. Potom mechanicky uplatníme posloupnost jedenácti kroků získanou zkoušením, která dostane 4 na své místo, přičemž dočasně přemístí i kamínek 3. Podobně postupujeme v případě 8, 13 a 14: posloupnosti kroků jsou v proměnných Kroky4, Kroky8, Kroky13 a Kroky14 a simuluje je procedura Perm2x3 (za svůj název vděčí tomu, že permutuje oblast velikosti 2x3 pozic).

Program nejprve vypočítá posloupnost kroků vedoucí na K (příp. N') do pole Kroky a ověří (proměnná Resitelne), zda je počáteční situace řešitelná. Jestliže ano, obnoví počáteční situaci (z proměnné PuvodniPlocha) a předvede nalezené řešení.

Pro dokončení popisu ještě potřebujeme odhadnout počet kroků řešení, abychom uměli nadefinovat typ TKroky. Podíváme se nejprve na provádění cyklu Cykly[Ktery] délky d procedurou Cykluj(Ktery,Kam,nP). Rozmístění kamínků na tomto cyklu se během provádění mění, ale všech možných rozmístění je d(d-1), neboť rozmístění je určeno polohou kamínku Ktery a polohou prázdného políčka. To znamená, že Cykluj(Ktery,Kam,nP) provede nanejvýš d(d-1) kroků. Z tabulky tedy určíme, že celkový počet kroků přidaných do pole Kroky typu TKroky procedurou Cykluj je 16.15+2.14.13+2.12.11+2.10.9+2.8.7+2.6.5+2.4.3=1254. K tomuto číslu ještě musíme přičíst korekci pro kamínky 2 a 6 (celkem 6 kroků) a 4 provedení Perm2x3 (celkem 44 kroků), což dohromady dává 1304 kroků. Konstantu MaxKroky=1400 určující velikost pole TKroky jsme trochu nadsadili.

Program v jazyku Turbo Pascal

program Patnact; uses Crt; const MaxKroky = 1400; type TKamen = 0..15; TPozice = 1..16; TPlocha = array [TPozice] of TKamen; TKroky = array [1..MaxKroky] of TPozice; TCykly = array [TKamen] of array [TPozice] of 0..16; T2x3 = array [1..11] of 0..16; var Plocha, PuvodniPlocha: TPlocha; Kroky: TKroky; CisloKroku, PocetKroku: 0..MaxKroky; Vstup, Vystup: Text; Resitelne: boolean; { KRESLENI } procedure Vykresli(p: TPozice); begin gotoxy(3 + 8 * ((p - 1) mod 4), 3 + 4 * ((p - 1) div 4)); if (plocha[p] > 0) then write(plocha[p]:3, ' ') else write(' ':4); end; procedure V{odorovne cary}; begin writeln(' ------- ------- ------- ------- '); end; procedure Z{visle cary}; begin writeln('| | | | |'); end; procedure VykresliPlochu; var p: TPozice; begin ClrScr; V;Z;Z;Z;V;Z;Z;Z;V;Z;Z;Z;V;Z;Z;Z;V; for p := 1 to 16 do Vykresli(p); end; { KROKY RESENI } function NajdiPrazdnouPozici: TPozice; var p: TPozice; begin for p := 1 to 16 do if plocha[p] = 0 then NajdiPrazdnouPozici := p; end; procedure UdelejKrok(Odkud: TPozice); var Kam: TPozice; begin Kam := NajdiPrazdnouPozici; Plocha[Kam] := Plocha[Odkud]; Plocha[Odkud] := 0; Vykresli(Odkud); Vykresli(Kam); end; function NasledujiciKrok: TPozice; begin inc(CisloKroku); NasledujiciKrok := Kroky[CisloKroku]; end; { RESENI HRY } const Cykly: TCykly = ( {nepotrebne} (0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0), { 1-> 1 } (2,3,4,8, 1,10,6,12, 5,14,7,16, 9,13,11,15), { 2-> 2 } (0,3,7,0, 6,2,8,12, 5,14,10,16, 9,13,11,15), { 3-> 3 } (0,0,4,8, 6,7,3,12, 5,14,10,16, 9,13,11,15), { 4-> 8 } (0,0,0,0, 6,7,8,12, 5,14,10,16, 9,13,11,15), { 5-> 5 } (0,0,0,0, 6,7,8,12, 5,14,10,16, 9,13,11,15), { 6-> 6 } (0,0,0,0, 0,7,11,0, 10,6,12,16, 9,13,14,15), { 7-> 7 } (0,0,0,0, 0,0,8,12, 10,11,7,16, 9,13,14,15), { 8->12 } (0,0,0,0, 0,0,0,0, 10,11,12,16, 9,13,14,15), { 9-> 9 } (0,0,0,0, 0,0,0,0, 13,9,10,11, 14,15,16,12), { 10->10 } (0,0,0,0, 0,0,0,0, 0,14,10,11, 0,15,16,12), { 11->11 } (0,0,0,0, 0,0,0,0, 0,0,12,16, 0,0,11,15), {nepotrebne} (0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0), { 13->14 } (0,0,0,0, 0,0,0,0, 0,14,10,11, 0,15,16,12), { 14->15 } (0,0,0,0, 0,0,0,0, 0,0,15,11, 0,0,16,12), {nepotrebne} (0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0) ); Kroky4: T2x3 = ( 8, 4, 3, 7, 8,12,11, 7, 3, 4, 8); Kroky8: T2x3 = (12, 8, 7,11,12,16,15,11, 7, 8,12); Kroky13: T2x3 = (14,13, 9,10,14,15,11,10, 9,13,14); Kroky14: T2x3 = (15,14,10,11,15,16,12,11,10,14,15); procedure PridejKrok(Odkud, Kam: TPozice); begin inc(PocetKroku); Kroky[PocetKroku] := Odkud; Plocha[Kam] := Plocha[Odkud]; Plocha[Odkud] := 0; end; procedure Cykluj(Ktery: TKamen; Kam: TPozice; nechPrazdnou: TPozice); var Prazdna: TPozice; begin while (Plocha[Kam] <> Ktery) or (Plocha[nechPrazdnou] <> 0) do begin Prazdna := NajdiPrazdnouPozici; PridejKrok(Cykly[Ktery][Prazdna], Prazdna); end; end; procedure Perm2x3(var Kroky2x3: T2x3); var i: integer; begin for i := 1 to 11 do PridejKrok(Kroky2x3[i], NajdiPrazdnouPozici); end; procedure Vyres15; begin Cykluj(1,1,2); if (Plocha[4] = 2) then begin PridejKrok(3,2); PridejKrok(4,3); PridejKrok(8,4); end; Cykluj(2,2,3); Cykluj(3,3,8); if (Plocha[4] <> 4) then begin Cykluj(4,8,12); Perm2x3(Kroky4); end; Cykluj(5,5,6); if (Plocha[8] = 6) then begin PridejKrok(7,6); PridejKrok(8,7); PridejKrok(12,8); end; Cykluj(6,6,7); Cykluj(7,7,12); if (Plocha[8] <> 8) then begin Cykluj(8,12,16); Perm2x3(Kroky8); end; Cykluj(9,9,14); if (Plocha[13] <> 13) then begin Cykluj(13,14,15); Perm2x3(Kroky13); end; Cykluj(10,10,15); if (Plocha[14] <> 14) then begin Cykluj(14,15,16); Perm2x3(Kroky14); end; Cykluj(11,11,16); Resitelne := (Plocha[15] = 15); end; { HLAVNI PROCEDURY } procedure Inicializuj; var i,j,k : integer; begin assign(Vstup, 'P-I-1.inp'); reset(Vstup); for i := 1 to 16 do read(Vstup, Plocha[i]); close(Vstup); PuvodniPlocha := Plocha; PocetKroku := 0; end; procedure VypisVysledky; begin assign(Vystup, 'P-I-1.out'); rewrite(Vystup); if (Resitelne) then for CisloKroku := 1 to PocetKroku do write(Vystup, ' ', Kroky[CisloKroku]) else write(Vystup, 'Nema reseni'); close(Vystup); end; procedure PredvedReseni; var ch: char; begin Plocha := PuvodniPlocha; CisloKroku := 0; VykresliPlochu; gotoxy(1,25); write('Stiskni libovolnou klavesu (q = konec)'); ch := ReadKey; while (CisloKroku < PocetKroku) and (ch <> 'q') do begin UdelejKrok(NasledujiciKrok); gotoxy(1,24); write('Krok ', CisloKroku, ' (z ', PocetKroku, ')'); ch := ReadKey; end; if (CisloKroku = PocetKroku) then write(' --- hotovo!'); end; begin Inicializuj; Vyres15; VypisVysledky; if (Resitelne) then PredvedReseni; end.

P-I-2

Nechť A[1], A[2],..., A[m] jsou body první množiny, B[1], B[2],..., B[n] jsou body druhé množiny, m,n >= 1. Na souřadnice bodů těchto množin se budeme odvolávat pomocí tečkové notace, tj. A[k].x je x-ová souřadnice a A[k].y je y-ová souřadnice bodu A[k].

Jestliže m=1 a zároveň n=1, pak rozlišíme dva případy:

a) body A[1] a B[1] jsou totožné, a proto množiny nejsou separovatelné

b) body A[1] a B[1] jsou různé, tedy množiny jsou separovatelné, což je vyřešeno v následujících okrajových případech. Oddělující přímka může procházet jedním z nich.

Bez újmy na obecnosti předpokládejme, že m>1 (jinak je možné množiny přeznačit).

Vyřešíme ještě okrajové případy:

a) když A[m].x < B[1].x, potom oddělující přímkou je x=A[m].x

b) když B[n].x < A[1].x, potom oddělující přímkou je x=B[n].x

c) když A[1].y < B[n].y, potom oddělující přímkou je y=A[1].y

d) když B[1].y < A[m].y, potom oddělující přímkou je y=B[1].y.

Další řešení závisí na tom, s jakou výpočetní složitostí chceme počítat.

Kubická složitost

Toto triviální řešení je založeno na myšlence, že oddělující přímka bude určena dvěma body téže množiny (může na ní ležet i víc bodů téže množiny). Pro všechny dvojice bodů množiny A budeme postupně vytvářet přímky a otestujeme, zda zbývající body množiny A leží v opačné polorovině, než všechny body množiny B. Poté celý postup zopakujeme s tím, že vyměníme množiny A a B. Vyhovující přímka je řešením úlohy. V nejhorším případě je třeba přezkoumat všechny možné přímky vytvářené body množiny A a všechny možné přímky určené body množiny B. Za předpokladu, že m < n, je časová složitost tohoto řešení O(n3).

Kvadratická složitost

Řešení je založeno na myšlence, že oddělující přímka je určena úsečkou konvexního obalu množiny A nebo úsečkou konvexního obalu množiny B. Konvexní obal je možné sestrojit v lineárním čase vzhledem k tomu, že body jsou uspořádány podle x-ových souřadnic. Počet úseček konvexního obalu může být nejvýše m pro množinu A a n pro množinu B. Další postup je stejný jako v předcházejícím případě, pro každou úsečku konvexního obalu množiny A a konvexního obalu množiny B otestujeme, zda body množiny A leží v opačné polorovině než body množiny B. Protože počet zkoumaných úseček je lineární, časová složitost tohoto řešení je O(n2).

Lineární složitost

Řešení navazuje na řešení s kvadratickou složitostí, tj. je třeba vytvořit konvexní obaly obou množin a ty potom konstantním počtem průchodů zpracovat, což povede k lineární časové složitosti.

Podrobnější postup řešení s lineární složitostí

  1. Vytvoření konvexního obalu množiny A
    Vzhledem ke tvaru množin A, B je to jednodušší než v případě obecného tvaru množiny (body jsou již utříděné). Konvexní obal množiny A bude tvořen dvěma polygony Ap[1]=A[1], Ap[2],..., Ap[vap]=A[m] je horní polygon a Am[1]=A[1], Am[2],..., Am[vam]=A[m] je dolní polygon konvexního obalu množiny A. Konvexní obal nebude obsahovat žádné zbytečné vrcholy, tj. každý vnitřní úhel konvexního obalu je menší než 180 stupňů. Tato část algoritmu vyžaduje lineární čas vzhledem k počtu bodů množiny A, tj. O(m).
  2. Zjistíme polohu bodu B[1] vzhledem ke konvexnímu obalu množiny A. Jestliže bod B[1] leží v konvexním obalu množiny A, pak množiny A a B nejsou separovatelné. Pokud bod B[1] neleží uvnitř konvexního obalu množiny A, potom známe aspoň jeden bod množiny B, který neleží uvnitř. Tato část algoritmu vyžaduje lineární čas vzhledem k počtu bodů množiny A, tj. O(m).
  3. Tento a následující kroky provedeme pouze v případě, že bod B[1] neleží v konvexním obalu množiny A.
    Vytvoříme konvexní obal množiny B, který bude tvořen dvěma polygony: Bp[1]=B[1], Bp[2],..., Bp[vbp]=B[n] je horní polygon a Bm[1]=B[1], Bm[2],...,Bm[vbm]=B[n] je dolní polygon. Tato část algoritmu vyžaduje lineární čas vzhledem k počtu bodů množiny B, tj. O(n).
  4. Určení společných bodů konvexního obalu množiny A a obalu množiny B. Známe čtyři polygony Ap: Ap[1],..., Ap[vap], Am: Am[1],..., Am[vam], Bp: Bp[1],..., Bp[vbp] a Bm: Bm[1],..., Bm[vbm]. Stačí zjistit průsečíky dvojic polygonů patřících k různým množinám (tj. čtyři dvojice). Jestliže se polygony neprotínají, potom množiny A a B jsou separovatelné. V opačném případě separovatelné nejsou. Průsečík dvou polygonů určujeme postupným průchodem úseček jednoho polygonu a z druhého polygonu přitom zkoumáme jen odpovídající část určenou x-ovými souřadnicemi vrcholů polygonu. Tato část algoritmu vyžaduje lineární čas vzhledem k počtu bodů obou množin, tzn. O(m+n).
  5. Určení takových dvou bodů obou konvexních obalů, které mají nejmenší vzdálenost. Tento krok se provádí jen v případě, že množiny jsou separovatelné.
    Uvažujme polygony Ap a Bm. Analogicky je možné provést výpočet pro dvojici polygonů Am a Bp. Nejprve je třeba určit, které polygony budeme uvažovat. Vypočítáme vzdálenost bodů Ap[1] a Bm[1]. Postupným průchodem přes úsečky Ap[i]-Ap[i+1] pro 1 <= i <= vap-1 budeme zpracovávat body Bm[1],..., Bm[vbm]. Vypočítáme vždy vzdálenost bodu od úsečky. Přechod na novou úsečku provedeme tehdy, když kolmice na právě zkoumanou úsečku vedená právě zkoumaným bodem nemá společný bod s touto úsečkou. Je potřeba pamatovat si údaje o vypočítané dosud minimální vzdálenosti a kterých bodů, resp. úsečky a bodu se tato vzdálenost týká. Postup je založen na myšlence, že daným bodem je možné vést ke konvexnímu obalu nejvýše jednu kolmici. Celý výpočet představuje jeden průchod množinou bodů Ap a jeden průchod množinou bodů Bm, proto tato část algoritmu bude pracovat v čase O(m+n).
  6. Určení oddělující přímky
    Předpokládejme, že tyto body leží na polygonech Ap a Bm. Analogický postup je pro jinou dvojici polygonů. Nechť C je bod konvexního obalu množiny A a D bod konvexního obalu množiny B, které určují nejmenší vzdálenost konvexních obalů. Označme tuto vzdálenost d.

    Mohou nastat dva případy:

    a) Bod D je vrcholem konvexního obalu množiny B, tj. D=Bm[r] a bod C leží uvnitř úsečky určené body Ap[t]-Ap[t+1]. (Analogické řešení pro situaci, když bod D leží na nějaké úsečce a bod C je vrchol konvexního obalu.)

    b) C a D jsou vrcholy konvexního obalu, tj. C=Ap[t] a D=Bm[r].

    V případě a) bude oddělující přímka určena body Ap[t] a Ap[t+1], nebo úsečkou Bm[r-1]-Bm[r] nebo úsečkou B[mr]-B[mr+1]. Pro body množiny A je to zřejmé, pro body množiny B ukážeme: Bod Bm[r] je separovaný správně. Žádný bod množiny B neleží v pásu obalujícím konvexní obal množiny A ve vzdálenosti d, d > 0. Protože body úsečky Bm[r-1]-Bm[r] nemohou ležet uvnitř obalujícího pásu, (mohou ležet nanejvýš na jeho hranici) platí, že její body jsou zvolenou přímkou správně separovány od bodů množiny A. Analogicky platí pro body úsečky Bm[r]-Bm[r+1]. Z konvexnosti množiny Bm vyplývá, že její zbývající body mají od zvolené přímky větší vzdálenost, tedy vybraná přímka je oddělující přímkou. Oddělující přímky určené úsečkami Bm[r-1]-Bm[r] a Bm[r]-Bm[r+1] je třeba uvažovat v hraničních případech r=1 nebo r=vbm. V případě b) bude oddělující přímka určena jednou z úseček s koncovými body v bodech C a D. Je to ta, která svírá s přímkou určenou body C a D největší úhel. Jsou-li určeny nejbližší body konvexních obalů, tato část algoritmu vyžaduje konstantní čas O(1).

Jestliže shrneme výsledky složitosti, dostáváme, že existuje algoritmus pracující v lineárním čase O(m+n).

Program Separovatelnost_mnozin; {Program určí přímku, která oddělí dvě oddělitelné množiny bodů. Jestliže množiny nejsou oddělitelné, podá o tom zprávu.} const nmax=100; {Maximalny pocet bodov v mnozinach} type bod=record {Zaznam pre jeden bod} x, y: real; {x-ova a y-ova suradnica bodu} end; prvok=record {Zaznam pre prvok zasobnika} bd:bod; {Ukladany bod} tg:real; {Charakteristika prislusnosti ku konv. obalu} zn:char; {Meno mnoziny A alebo B} end; mnoz=array[1..nmax] of bod; {Typ pre ulozenie mnoziny} zasobnik=array[1..nmax] of prvok;{Typ pre zasobnik, v ktorom su ukladane polygony konvexneho obalu} var A, B: mnoz; {Dane mnoziny} f: text; {Vstupny subor} m,n :integer; {Skutocne pocty prvkov v mnozinach, |A|=m, |B|=n} Ap, Am: zasobnik; {Zasobniky pre horny a dolny polygon konv. obalu mnoziny A} Bp, Bm: zasobnik; {Zasobniky pre horny a dolny polygon konv. obalu mnoziny B} vap, vam: integer; {Pocty bodov v polygonoch prisluchajucich A} vbp, vbm: integer; {Pocty bodov v polygonoch prisluchajucich B} ddd: real; {Minimalna vzdialenost konvex. obalov} aa, bb, cc: real; {Koeficienty separujucej priamky} i:integer; procedure Nacitaj (var A,B:mnoz; var m,n:integer); {Nacitanie poctov bodov a suradnic bodov oboch mnozin} var i:integer; begin Assign(f,'mnoz3.dat'); reset(f); writeln('Zadajte pocet prvkov prvej a druhej mnoziny'); readln(m,n); for i:=1 to m do readln(f,A[i].x, A[i].y); readln(f); for i:=1 to n do readln(f,B[i].x, B[i].y); end; {Nacitaj} function tga(C, D:bod):real; {Vypocet tangensu uhla pri vrchole C v pravouhlom trojuholniku, urcenom bodmi C, D a (C.x,D.y); C.xtgalf) do begin inc(t1); tgalf1:=tga(A[t1],A[1]); end; if t1<>m then begin inc(vm); Am[vm].bd:=A[t1]; Am[vm].tg:=tgalf1; end; t2:=2; {Hladanie prveho bodu , ktory by mohol patrit k hornemu polygonu} while (t2<m) and (tgalf2<tgalf) do begin inc(t2); tgalf1:=tga(A[t2],A[1]); end; if t2<>m then begin inc(vp); Ap[vp].bd:=A[t2]; Ap[vp].tg:=tgalf2; end; if t1<t2 then begin tmin:=t1; tmax:=t2 end else begin tmin:=t2; tmax:=t1 end; for t:=tmin+1 to m-1 do if t<>tmax then begin tgalf1:=tga(A[t],A[1]); if tgalf1<tgalf then {Bod patri do dolnej casti} Predlz(Am,vm,t,1) else {Bod patri do hornej casti} Predlz(Ap,vp,t,-1); end; {Zaradenie posledneho bodu} Predlz(Am,vm,m,1); Predlz(Ap,vp,m,-1); end; {Konv} function Spol_b_u(C,D:bod; E,F:bod):boolean; {Funkcia nadobudne hodnotu true, ak usecky C-D a E-F maju spolocny bod, inak nadobudne hodnotu false} var k1, q1, k2, q2:real; {Koeficienty priamok} P:bod; {Potencialny spolocny bod useciek} begin Priamka(C,D,k1,q1); Priamka(E,F,k2,q2); if (k1=k2) then begin {Priamky su rovnobezne} if (q1=q2) then begin {Priamky su totozne} if (F.x<C.x) or (E.x>D.x) then Spol_b_u:=false else Spol_b_u:=true; end else Spol_b_u:=false end else begin {Priamky su roznobezne} P.x:=(q2-q1)/(k1-k2); P.y:=k1*P.x+q1; if (P.x>=C.x) and (P.x<=D.x) and (P.x>=E.x) and (P.x<=F.x) then Spol_b_u:=true else Spol_b_u:=false; end; end; {Spol_b_u} function Lezi_v(Ap,Am:zasobnik; vap,vam:integer; C:bod):boolean; {Nadobudne hodnotu true, ak bod C lezi v konvexnom obale Ap a Am} var i, j: integer; k1, q1, k2, q2:real; y1, y2: real; q: boolean; begin i:=1; while (Ap[i].bd.x<C.x) and (i<=vap) do inc(i); if i>vap then {Bod C nelezi v konvexnom obale Ap a Am} q:=false else begin j:=1; while (C.x<Am[j].bd.x) and (j<=vam) do inc(j); {Uvazujeme usecky Ap[i-1]-Ap[i] a Am[j-1]-Am[j]} Priamka(Ap[i-1].bd,Ap[i].bd,k1,q1); Priamka(Am[j-1].bd,Am[j].bd,k2,q2); y1:=C.y-k1*C.x-q1; y2:=C.y-k2*C.x-q2; if (y2>=0) and (y1<=0) then q:=true else q:=false; end; Lezi_v:=q; writeln('lezi_v ',q); end; {Lezi_v} function Vzd_bodov(C,D:bod):real; {Vypocet Euklidovej vzdialenosti dvoch bodov C, D} begin Vzd_bodov:=sqrt(sqr(C.x-D.x)+sqr(C.y-D.y)) end; {Vzd_bodov} function Vzd_b_us(C:bod; D,E:bod; var vr:boolean; var PP:bod):real; {Vypocet vzdialenosti bodu C od usecky D-E} {vr nadobuda hodnotu true, ak najmensia vzdialenost je urcena kolmicou na usecku D-E, inak false} var kk, qq, qk: real; v, vd, ve: real; begin Priamka(D,E,kk,qq); {Priamka urcena bodmi D,E} qk:=C.y+C.x/kk; {Priamka kolma na D, E , prech. bodom C} PP.x:=(qk-qq)/(kk+1/kk); {x-ova suradnica paty kolmice PP} PP.y:=kk*PP.x+qq; {y-ova suradnica paty kolmice PP} v:=Vzd_bodov(C,PP); {Vzdialenost bodu C od priamky D-E} if (PP.x>=D.x) and (PP.x<=E.x) then begin {Bod PP je na usecke D-E} Vzd_b_us:=v; vr:=true end else begin {Bod PP nie je na usecke D, E} vd:=Vzd_bodov(C,D); ve:=Vzd_bodov(C,E); if vd<ve then begin Vzd_b_us:=vd; PP:=D end else begin Vzd_b_us:=ve; PP:=E end; vr:=false; end; end; {Vzd_b_us} function Vzd_polg(Ap,Bm:zasobnik; vap,vbm:integer; var i1,j1:integer):real; {Vypocet vzdialenosti dvoch polygonov} var i,j: integer; dd: real; dpom:real; vr: boolean; Pk: bod; {Pata kolmice } begin dd:=Vzd_bodov(Ap[1].bd, Bm[1].bd); i1:=1; j1:=1; i:=1; j:=1; while i<=vap-1 do begin while j<=vbm do begin dpom:= Vzd_b_us(Bm[j].bd,Ap[i].bd,Ap[i+1].bd,vr,Pk); if dpom<dd then begin dd:=dpom; if (Pk.x=Ap[i+1].bd.x) and (Pk.y=Ap[i+1].bd.y) then i1:=i+1 else i1:=i; j1:=j; end; if (not vr) and (i<vap) then inc(i) else inc(j); end; if j>=vbm then i:=vap; end; Vzd_polg:=dd; end; {Vzd_polg} function Pries_polg(Ap, Bm: zasobnik; vap,vbm: integer):boolean; {Funkcia nadobudne hodnotu true, ak polygony sa pretinaju, inak false} var i, j: integer; qq:boolean; begin i:=1; j:=1; qq:=false; while (i<=vap-1) and not qq do begin while (j<=vbm-1) and not qq do begin qq:= Spol_b_u(Ap[i].bd,Ap[i+1].bd,Bm[j].bd,Bm[j+1].bd); if not qq then if (Ap[i].bd.x>Bm[j].bd.x) and (Ap[i+1].bd.x<Bm[j+1].bd.x) then inc(i) else if (Ap[i].bd.x<Bm[j].bd.x) and (Ap[i+1].bd.x>Bm[j+1].bd.x) then inc(j) else begin inc(i); inc(j) end; if i>=vap then j:=vbm; end; if j>=vbm then i:=vap; end; Pries_polg:=qq; end; {Pries_polg} function Separ_polg(Ap,Am,Bp,Bm:zasobnik;vap,vam,vbp,vbm:integer):boolean; {Funkcia nadobudne hodnotu true, ak mnoziny A, B su separovatelne.} var q1, q2, q3, q4: boolean; begin q1:=Pries_polg(Ap,Bm, vap,vbm); q2:=Pries_polg(Am,Bm, vam,vbm); q3:=Pries_polg(Ap,Bp, vap,vbp); q4:=Pries_polg(Am,Bp, vam,vbp); Separ_polg:=not(q1 or q2 or q3 or q4); end; {Separ_polg} function Min_vzd_konv_ob(Ap,Am,Bp,Bm:zasobnik; vap,vam,vbp,vbm:integer; var Apom, Bpom: zasobnik; var vp1, vp2: integer; var i1, j1:integer):real; {Funkcia pocita minimalnu vzdialenost polygonov a body, ktore ju urcuju} var dd:real; ka, qa, kb, qb: real; yb1, ybn, ya1, yam: real; begin Priamka(A[1],A[m],ka,qa); Priamka(B[1],B[n],kb,qb); yb1:=B[1].y-ka*B[1].x-qa; ybn:=B[n].y-ka*B[n].x-qa; ya1:=A[1].y-kb*A[1].x-qb; yam:=A[m].y-kb*A[m].x-qb; if ((yb1>0) and (yb>>0)) or ((ya1>0) and (yam>0)) then begin Bpom:=Bm; vp1:=vbm; Apom:=Ap; vp2:=vap; end else if ((yb1<0) and (ybn<0)) or ((ya1<0) and (yam<0)) then begin Bpom:=Bp; vp1:=vbp; Apom:=Am; vp2:=vam; end; dd:=Vzd_polg(Apom,Bpom,vp2,vp1,i1,j1); Min_vzd_konv_ob:=dd; end; {Min_vzd_konv_ob} procedure Separ_priamka( var aa, bb, cc: real); {Procedura urci separujucu priamku v tvare aa*x+bb*y+cc=0} var PP: bod; vrr: boolean; kk, qq:real; dd:real; vp1, vp2: integer; Apom, Bpom: zasobnik; i1, j1: integer; qs: boolean; function Separ(C,D:bod;Apom:zasobnik;vp1:integer):boolean; {Funkcia nadobudne hodnotu true, ak vsetky body Apom lezia v tej istej polrovine urcenej priamkou C-D} var y1, y2: real; q:boolean; ii: integer; begin Priamka(C,D,kk,qq); y1:=kk*Apom[1].bd.x+qq; ii:=2; q:=true; while (ii<=vp1) and q do begin y2:=kk*Apom[ii].bd.x+qq; if ((y1>0) and (y2>0)) or ((y1<0) and (y2<0)) then q:=true else q:=false; inc(ii); end; Separ:=q; end; {Separ} begin ddd:=Min_vzd_konv_ob(Ap,Am,Bp,Bm,vap,vam,vbp,vbm,Apom,Bpom,vp1,vp2,i1,j1); dd:= Vzd_b_us(Bpom[j1].bd,Apom[i1].bd,Apom[i1+1].bd,vrr,PP); if (j1>1) and (j1<vp2) then if not Separ(Bpom[j1].bd,Bpom[j1+1].bd,Apom,vp1) then qs:= Separ(Bpom[j1-1].bd,Bpom[j1].bd,Apom,vp1); if (not qs) and (j1=1) then qs:= Separ(Bpom[j1].bd,Bpom[j1+1].bd,Apom,vp1); if (not qs) and (j1=vp2) then qs:= Separ(Bpom[j1-1].bd,Bpom[j1].bd,Apom,vp1); if not qs then if vrr then {Separujuca priamka je urcena bodmi Ap[i1], Ap[i1+1], alebo useckami Bpom[j1-1]-Bpom[j1] alebo Bpom[j1]-Bpom[j1+1] ak existuju} Priamka(Apom[i1].bd,Apom[i1+1].bd,kk,qq) else {Separujuca priamka je urcena bodom Ap[i1] alebo Bm[j1]} begin if (i1>1) and (i1<vp1) then if not Separ(Apom[i1].bd,Apom[i1+1].bd,Bpom,vp2) then qs:= Separ(Apom[i1-1].bd,Apom[i1].bd,Bpom,vp2); if (not qs) and (i1=1) then qs:= Separ(Apom[i1].bd,Apom[i1+1].bd,Bpom,vp2); if (not qs) and (i1=vp1) then qs:= Separ(Apom[i1-1].bd,Apom[i1].bd,Bpom,vp2); end; aa:=-kk; bb:=1; cc:=-qq; end; {Separ_priamka} begin {Hlavny program} Nacitaj(A,B,m,n); {Okrajove pripady} if B[1].x>A[m].x then writeln('Separujuca priamka je x=',A[m].x) else if B[n].y>A[1].y then writeln('Separujuca priamka je y=',A[1].y) else if A[1].x>B[n].x then writeln('Separujuca priamka je x=',B[n].x) else if A[m].y>B[1].y then writeln('Separujuca priamka je y=',B[1].y) else begin Konv(A,m,Ap,Am,vap,vam); if Lezi_v(Ap,Am,vap,vam, B[1]) then begin writeln('Bod B[1] lezi vo vnutri konv. obalu mnoziny A'); writeln(' Mnoziny nie su separovatelne'); end else begin readln; Konv(B,n,Bp,Bm,vbp,vbm); if Separ_polg(Ap,Am,Bp,Bm,vap,vam,vbp,vbm) then begin Separ_priamka(aa,bb,cc); writeln('Separujuca priamka: ',aa:7:2,'*x+',bb:7:2,'*y+',cc:7:2,'=0'); end else writeln(' Mnoziny nie su separovatelne'); end; end; readln; end.

P-I-3

Ze zadání úlohy je zřejmé, že bude vhodné spočítat si nejlepší "nepřímé" výměnné kurzy napřed (fáze předzpracování - složitost závisí na N, ale ne na P). Program pak může snadno odpovídat na otázky (složitost závisí na P, ale ne na N). Zavedeme proto (trojúhelníkovou) tabulku nejlepších nepřímých výměnných kurzů T[I,J] (1 <= I < J <= N), která bude výsledkem předzpracování. Nejprve popíšeme její prvky (co vlastně znamená, že nejlepší nepřímý výměnný kurz mezi měnami I a J je T[I,J]) a pokusíme se najít vztahy mezi těmito prvky, které nám umožní vytvořit algoritmus.

Výměnou budeme nazývat posloupnost V=(I0, I1,..., Ih) měn s vlastností I0 < I1 < ... < Ih, h >= 1. Tato výměna realizuje (nepřímý) převod měny I0 na měnu Ih prostřednictvím měn I1,...,Ih-1 (pro h=1 máme samozřejmě přímý převod). Za jednu jednotku měny I0 dostaneme po výměně V zřejmě K[I0,I1]K[I1,I2]...K[Ih-1,Ih] jednotek měny Ih - nazvěme toto číslo hodnotou H(V) výměny V.

Nejlepší výměnný kurz T[I,J] mezi měnami I a J nyní můžeme popsat jako maximální hodnotu mezi hodnotami všech výměn realizujících převod měny I na J: T[I,J]=max{H(V); V=(I0, I1,...,Ih), I=I0, J=Ih}.

Základním pozorováním pro řešení úlohy je následující tvrzení (princip optimality podvýměn): Jestliže nějaká výměna realizuje nejlepší výměnný kurz (nepřímý převod) mezi měnami I a J a v této výměně byla použita měna M, I < M < J, pak výměna I na M, resp. M na J musela být také optimální - použitím lepší výměny bychom vylepšili i výměnu I na J.

Formálně: Nechť výměna V=(I,...,M,...,J) má optimální hodnotu H(V)=T[I,J] a označme si V1=(I,...,M), V2=(M,...,J). Potom H(V1)=T[I,M] a H(V2)=T[M,J], tj. také "podvýměny" jsou optimální a samozřejmě H(V)=H(V1)H(V2).

Myšlenka algoritmu by už teď měla být jasná: budeme určovat nejlepší výměnné kurzy mezi měnami I a J postupně pro J-I=1, 2, 3,..., N-1. Hodnoty pro J-I=1 jsou samozřejmě přímé kurzy K[I,J]. Když už známe hodnoty T[I,J] pro J-I < Q, určíme T[I,J] pro J-I=Q jako minimální hodnotu mezi K[I,J], T[I,I+1]T[I+1,J], T[I,I+2]T[I+2,J],... T[I,J-1]T[J-1,J]. Správnost tohoto postupu zaručuje princip matematické indukce a výše uvedený princip optimality podvýměn.

Program můžeme vylepšit ještě tím, že místo dvou tabulek K a T budeme používat jen jednu - dvojrozměrné pole Kurzy. V tomto poli budou ze začátku zapsány hodnoty z tabulky K a postupně je budeme nahrazovat počítanými hodnotami z tabulky T. Prvky T počítáme po diagonálách: nejprve T[1,2], T[2,3],..., T[N-1,N], potom T[1,3], T[2,4],..., T[n-2,n], pak T[1,4], T[2,5],..., T[n-3,n], atd. až T[1,n]. Při výpočtu hodnoty T[I,J], která se potom uloží do Kurzy[I,J], použijeme hodnoty T[I,M] a T[M,J], uložené v poli Kurzy[I,M], resp. Kurzy[M,J] a hodnotu K[I,J] uloženou v Kurzy[I,J].

program OrientExpress; const maxn = 80; var kurzy: array [1..maxn, 1..maxn] of real; n: 1..maxn; p: integer; vstup, vystup : Text; procedure Inicializuj; var i,j: integer; begin assign(vstup, 'p-i-3.inp'); assign(vystup, 'p-i-3.out'); reset(vstup); rewrite(vystup); read(vstup, n); for i := 1 to n - 1 do begin kurzy[i,i] := 1.0; for j := i + 1 to n do read(vstup, kurzy[i,j]); end; read(vstup, p); end; procedure VypocitajKurzy; var d, i, j, l: 1..maxn; { dlzka cesty, pociatok cesty, koniec cesty, medzistanica } npk: real; { nepriamy kurz } begin for d := 2 to n - 1 do for i := 1 to n - d do begin j := i + d; for l := i + 1 to j - 1 do begin npk := kurzy[i, l] * kurzy[l, j]; if (kurzy[i, j] < npk) then kurzy[i, j] := npk; end; end; end; procedure VypisKurzy; var i, j: integer; begin while (p > 0) do begin read(vstup, i,j); write(vystup, kurzy[i,j]:0:2, ' '); p := p - 1; end; end; procedure Ukonci; begin close(vstup); close(vystup); end; begin Inicializuj; VypocitajKurzy; VypisKurzy; Ukonci; end.

P-I-4

Tato úloha není algoritmicky příliš náročná. Stačí si uvědomit, že potřebujeme jen vypočítat hodnoty výstupů hradel H1 až Hk (ty už jednoznačně určují hodnoty výstupů obvodu) a k tomu stačí jediný "průchod" uspořádanou množinou hradel H1, H2,..., Hk, neboť hodnota výstupu hradla závisí jen na hodnotách vstupů obvodu příp. na hodnotách výstupů hradel s menším pořadovým číslem. Přesněji:
Složitost algoritmu je zřejmě lineární v n+k+m.

Zajímavější je otázka vnitřní reprezentace obvodu a formát textového popisu obvodu. Pěkné (ale pro dané účely zbytečně komplikované) řešení bychom mohli zapsat objektovými jazykovými prostředky. Uvedeme zde ale jednodušší řešení v jazyce Turbo Pascal, které objektové rysy jazyka nepoužívá.

Vnitřní reprezentace obvodu: Jednotlivá hradla budeme reprezentovat záznamem, celý obvod bude uložen jako pole těchto záznamů. Záznam typu Hradlo obsahuje typ hradla (kromě NAND, NOR a NOT také "falešná" hradla typu IN a OUT - vstupy a výstupy obvodu), indexy Vstup1, Vstup2 do pole hradel určující vstupy hradla a položku Vystup s možnými hodnotami 0/1 pro hodnotu výstupu hradla. Pro hradla typu IN je hodnota indexů Vstup1, Vstup2 nezajímavá a nastavuje se na 0. Pro hradla typu OUT hodnota indexu Vstup1 určuje "napojení" daného výstupu obvodu, položka Vstup2 se nepoužívá.

Chování hradel popisuje pole CH, které pro každý typ hradla (NAND, NOR a NOT) obsahuje tabulku příslušné boolské funkce. Logické hodnoty můžeme reprezentovat typem 0..1 (a ne boolean), jak je to obvyklé v logických obvodech. Abychom nemuseli rozlišovat hradla s jedním a se dvěma vstupy, všechna považujeme za dvojvstupová, přičemž druhý vstup hradla typu NOT je ztotožněn s jeho prvním vstupem - výpočet výstupní hodnoty to neovlivní.

Formát popisu obvodu: Popis obvodu začíná trojicí čísel N, K, M na samostatném řádku: počet vstupů/hradel/výstupů obvodu. Následují popisy K hradel a potom M výstupů (vstupy se dále nepopisují). Popis hradla/výstupu je tvaru
NAND vstup1 vstup2
NOR vstup1 vstup2
NOT vstup1
OUT vstup1,
kde vstup1 a vstup2 má jeden z dvou možných tvarů:

V popisu se mohou vyskytovat mezery, tabelátory a znaky konce řádku na libovolném místě (kromě "klíčových slov" NAND, NOR, NOT, OUT). Popis musí vyhovovat podmínkám úlohy: v popisu i-tého hradla se nesmí vyskytnout odvolávka na hradlo Hj s j >= i.

Řešení úlohy b

Je jasné, že výstup c se dá spočítat jako NOT (x NAND y). Všimněte si, že c OR (x NOR y) je přesně NOT s, tedy s vypočítáme jako c NOR (x NOR y). Zápis v navrženém formátu popisu obvodu:
2 4 2 NAND I1 I2 NOR I1 I2 NOT H1 NOR H2 H3 OUT H4 OUT H3 Schéma obvodu je názorně nakresleno na obrázku:
Schéma obvodu
program KombinacnyObvod; const max = 100; type Tabulka = array [0..1, 0..1] of 0..1; TypHradla = (H_NOT, H_NAND, H_NOR, H_IN, H_OUT); Hradlo = record typ: TypHradla; vstup1, vstup2: 0..max; vystup: 0..1; end; var n, k, m, p: integer; vstupnySubor, vystupnySubor: Text; CH: array [H_NOT..H_NOR] of Tabulka; hradla: array [1..max] of Hradlo; function medzera(c: char) : boolean; begin medzera := c in [#9, #10, #13, ' ']; end; function citajZnak(var f: Text) : char; var c: char; begin repeat read(f,c) until not medzera(c); citajZnak := c; end; procedure citajRetazec(var f: Text; var s: String); var c: char; begin s := ''; c := citajZnak(f); while not eof(f) and not medzera(c) do begin s := s + c; read(f, c); end; end; procedure Inicializuj; var i: integer; typ: string; typvstupu: char; begin CH[H_NOT] [0,0] := 1; CH[H_NOT] [1,1] := 0; CH[H_NOR] [0,0] := 1; CH[H_NOR] [0,1] := 0; CH[H_NOR] [1,0] := 0; CH[H_NOR] [1,1] := 0; CH[H_NAND][0,0] := 1; CH[H_NAND][0,1] := 1; CH[H_NAND][1,0] := 1; CH[H_NAND][1,1] := 0; assign(vstupnySubor, 'p-i-4.inp'); assign(vystupnySubor, 'p-i-4.out'); reset(vstupnySubor); rewrite(vystupnySubor); readln(vstupnySubor, n, k, m); for i := 1 to n do { vstupy obvodu } hradla[i].typ := H_IN; for i := n + 1 to n + k do begin { hradla obvodu } citajRetazec(vstupnySubor, typ); typvstupu := citajZnak(vstupnySubor); read(vstupnySubor, hradla[i].vstup1); if (typvstupu = 'H') then hradla[i].vstup1 := hradla[i].vstup1 + n; if (typ = 'NOT') then begin hradla[i].typ := H_NOT; hradla[i].vstup2 := hradla[i].vstup1; end else begin if (typ = 'NAND') then hradla[i].typ := H_NAND; if (typ = 'NOR') then hradla[i].typ := H_NOR; typvstupu := citajZnak(vstupnySubor); read(vstupnySubor, hradla[i].vstup2); if (typvstupu = 'H') then hradla[i].vstup2 := hradla[i].vstup2 + n; end; end; for i := n + k + 1 to n + k + m do begin { vystupy obvodu } hradla[i].typ := H_OUT; citajRetazec(vstupnySubor, typ); typvstupu := citajZnak(vstupnySubor); read(vstupnySubor, hradla[i].vstup1); if (typvstupu = 'H') then hradla[i].vstup1 := hradla[i].vstup1 + n; end; read(vstupnySubor, p); { pocet testovacich vstupov } end; procedure nastavVstupy; var i: integer; begin for i := 1 to n do read(vstupnySubor, hradla[i].vystup); end; procedure nastavHradla; var i: integer; x, y: 0..1; begin for i := n + 1 to n + k do begin x := hradla[hradla[i].vstup1].vystup; y := hradla[hradla[i].vstup2].vystup; hradla[i].vystup:= CH[hradla[i].typ][x,y]; end; end; procedure vypisVystupy; var i: integer; begin for i := n + k + 1 to n + k + m do begin hradla[i].vystup:= hradla[hradla[i].vstup1].vystup; write(vystupnySubor, hradla[i].vystup, ' '); end; writeln(vystupnySubor); end; procedure Ukonci; begin close(vstupnySubor); close(vystupnySubor); end; procedure Simuluj; begin while (p > 0) do begin nastavVstupy; nastavHradla; vypisVystupy; p := p - 1; end; end; begin Inicializuj; Simuluj; Ukonci; end.