Matematická olympiáda – kategorie P

Řešení úloh oblastního kola 47. ročníku

P-II-1 Druhý večírek

Jedná se o standardní úlohu teorie grafů nalézt maximální párování v bipartitním grafu. Muži tvoří jednu skupinu vrcholů grafu, ženy druhou. Hrany jsou v grafu umístěny mezi těmi dvojicemi vrcholů, kdy muž zná nějakou ženu. Jsou-li na vstupu zadány také dvojice mužů, kteří se navzájem znají, jsou tyto údaje ignorovány, neboť pro řešení úlohy jsou zcela nepodstatné. Totéž se týká dvojic žen. Maximálním párováním rozumíme co největší takovou množinu hran grafu, aby žádné dvě z nich neměly společný vrchol. Velikost maximálního párování v našem grafu určuje největší počet zároveň tančících párů na večírku.

Algoritmus řešení úlohy vychází od nějakého (libovolného) výchozího párování, které se pak postupně vylepšuje. Dokud to jde, v každém kroku se zvětší o jednu hranu. Za výchozí párování můžeme vzít jednoduše prázdnou množinu hran. Zbývá ukázat, jak lze existující párování zvětšit o jednu hranu nebo případně zjistit, že párování je již maximální. Budeme v grafu vyhledávat tzv. zlepšující cesty. Zlepšující cestou je taková posloupnost vrcholů grafu V1, V2,..., Vn, v níž mezi každými dvěma sousedními vrcholy vede hrana, tyto hrany střídavě jsou/nejsou zařazeny do momentálně existujícího párování, první a posledních z nich v párování nejsou a z vrcholů V1 a Vn ani nevede jiná hrana zařazená do párování. Z uvedených podmínek plyne, že n je sudé a že tedy mezi V1 a Vn jsou jeden muž a jedna žena. Nalezená zlepšující cesta má lichý počet hran (je jich n-1), z nichž (n-2)/2 je v současném párování a n/2 není v současném párování. Stačí nyní u všech hran zlepšující cesty změnit jejich náležení do momentálně existujícího párování. Z vlastností zlepšující cesty plyne, že tím získáme opět párování a to že bude mít o jednu hranu více, než dosavadní párování. Pokud žádná zlepšující cesta neexistuje, je momentální párování již maximální.

V následujícím programu je informace o vytvářeném párování uložena v poli P, kde je pro každou ženu zaznamenáno číslo jejího partnera, resp. 0 pokud dosud partnera nemá. Na začátku výpočtu jsou v P samé nuly. Postupně procházíme seznamem všech mužů a každého se vždy snažíme prostřednictvím rekurzivní funkce Cesta zařadit do průběžně vytvářeného párování. Pokud uspějeme, zvýšíme počítadlo V evidující počet již vytvořených párů. Funkce Cesta hledá postupně mezi ženami první takovou, s níž se nově zařazovaný muž zná a která buď dosud nemá žádného partnera, nebo již nějakého partnera má (tzn. je již zařazena s někým jiným do párování), ale ten je schopen nalézt si jinou partnerku. To se zjišťuje použitím rekurzivního volání funkce Cesta. V případě úspěšného nalezení ženy uvedených vlastností s ní nově přidávaný muž vytvoří pár.

V rekurzivní funkci Cesta je velmi důležité sledovat, aby posloupnost vnořených rekurzivních volání nevedla k zacyklení, tzn. aby se na zlepšující cestě žádný vrchol neopakoval. K tomu slouží množinová proměnná S, jež obsahuje v každém okamžiku čísla těch žen, které se již účastní právě zkoumané zlepšující cesty. Muž, který pomocí rekurzivního volání funkce Cesta zkoumá možnost nalezení jiné partnerky, než jakou má dosud přiřazenou, neobrací se na ty ženy, které jsou momentálně zařazeny do množiny S. Bez tohoto mechanismu by došlo k zacyklení výpočtu například pro vstupní data M=3, Z=2 a dvojice známých 1 -1, 1 -2, 2 -1, 2 -2, 3 -1.

program Vecirek2; {maximální párování v bipartitním grafu} const MaxM=100; {maximální počet mužů} MaxZ=100; {maximální počet žen} var A: array[1..MaxM, 1..MaxZ] of boolean; {známosti} M: 1..MaxM; {počet mužů} Z: 1..MaxZ; {počet žen} P: array[1..MaxZ] of 0..MaxM; {partneři žen} S: set of 1..MaxZ; {ženy na zlepšující cestě} V: integer; {výsledný počet párů} i, j: integer; {pomocné} function Cesta(C: integer): boolean; {určení zlepšující cesty, která začíná mužem číslo C} {vrací informaci, zda byla zlepšující cesta nalezena} var J: integer; begin Cesta:=false; for J:=1 to Z do if A[C,J] then if P[J]=0 then {žena J nemá partnera} begin {zařadit hranu C-J do párování} P[J]:=C; Cesta:=true; exit end else if not (J in S) then {žena J není na zlepšující cestě} begin S:=S+[J]; if Cesta(P[J]) then begin {partner ženy J si našel někoho jiného} P[J]:=C; {C bude novým partnerem ženy J} Cesta:=true; S:=S-[J]; exit end else S:=S-[J] end end; {Cesta} begin {vstup dat a inicializace:} write('Počet mužů: '); readln(M); write('Počet žen: '); readln(Z); writeln('Dvojice známých - muži kladnými čísly od 1 do ',M); writeln(' ženy zápornými čísly od -1 do -',Z); for i:=1 to M do for j:=1 to Z do A[i,j]:=false; while not eof do begin read(i,j); if (i>0) and (j<0) then A[i,-j]:=true; if (i<0) and (j>0) then A[j,-i]:=true; end; for j:=1 to Z do P[j]:=0; V:=0; S:=[]; {hledání zlepšujících cest:} for i:=1 to M do if Cesta(i) then V:=V+1; writeln('Maximální počet současně tančících párů: ', V) end.

P-II-2 Pokleslá podposloupnost

Zadanou posloupnost čísel si uložíme do pole A. Další dvě celočíselná pole B, C stejné velikosti (tzn. indexovaná od 1 do N) budeme používat při výpočtu jako pracovní. Hodnota B[i] bude představovat délku maximální neklesající podposloupnosti vybrané z posloupnosti A[i], A[i+1], ..., A[N], zatímco hodnota C[i] určuje délku maximální podposloupnosti s právě jedním poklesem vybrané z posloupnosti A[i], A[i+1], ..., A[N]. Jednotlivé hodnoty B[i], C[i] snadno určíme odzadu, tzn. v pořadí indexů N, N-1, ..., 1. Pro stanovení údajů B[i] a C[i] pro určité konkrétní i stačí jednou sekvenčně projít úseky polí A, B, C od indexu i+1 do N. Způsob výpočtu těchto hodnot ukazuje názorně programová ukázka. Hledaná délka maximální podposloupnosti s nejvýše jedním poklesem je rovna maximu z hodnot uložených v polích B, C (buď využijeme možnost jednoho poklesu, nebo nikoliv).

Pro určení B[i], C[i] pro jeden konkrétní index i vykonáme řádově N operací. To se opakuje celkem N-krát (pro jednotlivé indexy i). Algoritmus má proto kvadratickou časovou složitost, vyžaduje provést řádově O(N2) operací.

program Max_1_pokles; {Program určí v zadané posloupnosti celých čísel délku nejdelší vybrané podposloupnosti s nejvýše jedním poklesem.} const MaxN=1000; {maximální počet čísel} var A,B,C: array[1..MaxN] of integer; {A - zadaná posloupnost čísel, B - délka max. neklesajícího úseku, C - délka max. úseku s právě jedním poklesem} N: integer; {počet čísel} V: integer; {výsledná délka max. podposloupnosti} I, J: integer; begin write('Počet čísel: '); read(N); if N=0 then V:=0 else begin writeln('Posloupnost čísel:'); for I:=1 to N do begin read(A[I]); B[I]:=1; C[I]:=0 end; V:=1 end; for I:=N-1 downto 1 do {stanovení hodnot B[I], C[I]} for J:=I+1 to N do {zkoumáme možnost navázání A[I]} if A[I] > A[J] then {zde nastane jediný pokles} begin if C[I] < B[J]+1 then begin C[I]:=B[J]+1; if C[I] > V then V:=C[I] end end else {zde lze navázat bez poklesu} begin if B[I] < B[J]+1 then begin B[I]:=B[J]+1; if B[I] > V then V:=B[I] end; if C[I] < C[J]+1 then begin C[I]:=C[J]+1; if C[I] > V then V:=C[I] end end; writeln('Délka nejdelší vybrané podposloupnosti'); writeln('s nejvýše jedním poklesem: ',V) end.

P-II-3 Maximální okno

Obrazovku v systému MO-P-Windows si můžeme představit jako matici tvořenou 300x200 prvky, v níž každý prvek nese informaci, zda je příslušný bod obrazovky volný pro zobrazení nového okna nebo zda je již nějakým starším oknem "obsazen". Označíme-li si volné body hodnotou 1 a obsazené číslem 0, pak zadaná úloha vlastně představuje úkol nalézt v matici tvořené prvky 0 a 1 co největší obdélník tvořený samými jedničkami. Bylo by však velmi nešikovné a neefektivní testovat zvlášť každý obdélníkový výřez matice, zda neobsahuje nějakou nulu. Místo toho se nám vyplatí provést nejprve pomocný předvýpočet a spočítat si pro každou jedničku v matici počet jedniček nacházejících se v souvislé řadě nad ní a počet jedniček v souvislé řadě pod ní. Při návrhu výsledného algoritmu ještě využijeme skutečnosti, že maximální jedničková podmatice se musí svým levým okrajem dotýkat buď levého okraje celé matice, nebo nějaké nuly. V opačném případě by totiž nebyla maximální, bylo by možné zvětšit ji směrem doleva.

Při řešení úlohy budeme postupovat následovně. Nejprve načteme vstupní data a na jejich základě do matice A uložíme informaci, které body na obrazovce jsou volné a které obsazené. Potom provede předvýpočet a do matic U a L spočteme délky souvislých sloupců jedniček. Je-li prvek Ai,j nulový, zůstanou nulové také Ui,j a Li,j. V opačném případě udává Ui,j délku souvislé řady jedniček od prvku Ai,j směrem nahoru a podobně Li,j délku souvislé řady jedniček od Ai,j dolů. Předvýpočet se provede velmi snadno a rychle jedním průchodem po sloupcích matice A shora dolů a jedním průchodem po sloupcích matice směrem zdola nahoru. Při vlastním hledání maximální jedničkové podmatice pak budeme procházet maticí A postupně po řádcích. Pro každý nulový prvek Ai,j budeme hledat maximální jedničkový obdélník přiléhající k této nule svým levým okrajem. Postupujme od prvku Ai,j směrem doprava (tj. po prvcích Ai,j+1, Ai,j+2,...), dokud nenarazíme opět na nulu. Ta zprava omezuje "nejširší" jedničkový obdélník přiléhající levou stranou k prvku Ai,j. Pro každý prvek Ai,j+b=1, který cestou potkáme, určíme maximální jedničkový obdélník přiléhající levou stranou k prvku Ai,j takový, že jeho pravá strana je ve sloupci j+b. Jeho levý a pravý okraj je již omezen (hodnotami j a j+b), zbývá tedy určit pouze jeho horní a dolní okraj. Horní okraj se snažíme posunout "co nejvýš", dolní "co nejníže". Pro průběžné určování horního a dolního okraje maximálního jedničkového obdélníka přiléhajícího levou stranou k prvku Ai,j nyní výhodně použijeme informace předem spočítané a uložené v polích U a L.

Konečnost algoritmu je zřejmá, správnost plyne z toho, že algoritmus určí ke každé nule v matici A maximální jedničkový obdélník přiléhající k ní levou stranou; mezi všemi těmito obdélníky musí být i největší z jedničkových obdélníků. Časová složitost popsaného algoritmu je velmi příznivá, pouze O(nm). První fáze (předvýpočet) má evidentně složitost O(nm). Druhá fáze (vlastní výpočet) ovšem představuje jediný průchod maticí o nm prvcích po řádcích a má tedy také složitost pouze O(nm).

V programové realizaci v Turbo Pascalu je třeba vyřešit některé technické problémy vyplývající ze způsobu alokace paměti. Tři pole velikosti 300x200 bytů se nevejdou do jednoho datového segmentu určeného pro staticky alokované proměnné hlavního programu, a proto je musíme alokovat dynamicky a odkazovat se na ně z programu pomocí ukazatele.

program Maximalni_Okno; {Program hledá na obrazovce umístění maximálního okna, které nebude překrývat žádné z dříve zobrazených oken} const MaxX=299; {velikost obrazovky 0..MaxX,0..MaxY} MaxY=199; type Matice=array[-1..MaxX+1,-1..MaxY+1] of byte; {matice s okrajovým pásem kolem dokola} var A,L,U:^Matice; {z paměťových důvodů alokovány dynamicky} N:integer; {počet již zobrazených oken} x1,y1,x2,y2:integer; {souřadnice okna} MinL,MinU:integer; {minima počtů jedniček pod a nad} Vel:integer; {velikost zkoumaného okna} MaxVel:integer; {velikost maximálního okna} i,j,k:integer; begin {Načtení stavu obrazovky:} new(A); for i:=0 to MaxX do for j:=0 to MaxY do A^[i,j]:=1; {zatím je všude volno} write('Počet oken: '); read(N); {počet oken} writeln('Souřadnice rohů oken:'); for k:=1 to N do begin read(x1,y1,x2,y2); {souřadnice okna} for i:=x1 to x2 do for j:=y1 to y2 do A^[i,j]:=0; {obsazeno oknem} end; {Vytvoření pásu nul kolem dokola obrazovky:} for i:=-1 to MaxX+1 do begin A^[i,-1]:=0; A^[i,MaxY+1]:=0 end; for j:=-1 to MaxY+1 do begin A^[-1,j]:=0; A^[MaxX+1,j]:=0 end; { 1. fáze } new(L); new(U); for i:=0 to MaxX do begin for j:=MaxY+1 downto 0 do if A^[i,j]=0 then L^[i,j]:=0 else L^[i,j]:=L^[i,j+1]+1; {jednička nad jedničkami} for j:=-1 to MaxY do if A^[i,j]=0 then U^[i,j]:=0 else U^[i,j]:=U^[i,j-1]+1; {jednička pod jedničkami} end; { 2. fáze } MaxVel:=0; x1:=0; y1:=0; x2:=0; y2:=0; for j:=0 to MaxY do for i:=-1 to MaxX-1 do if A^[i,j]=0 then begin {projdi jedničky vpravo od A^[i,j]} k:=1; MinL:=maxint; MinU:=maxint; while A^[i+k,j]=1 do begin if L^[i+k,j]<MinL then MinL:=L^[i+k,j]; if U^[i+k,j]<MinU then MinU:=U^[i+k,j]; Vel:=k*(MinL+MinU-1); if Vel>MaxVel then begin {uschovej nové maximum} MaxVel:=Vel; x1:=i+1; x2:=i+k; y1:=j-MinU+1; y2:=j+MinL-1 end; k:=k+1 end end; { Tisk výsledku } write('Umístění nového maximálního okna'); writeln(x1, ' ', y1, ' ', x2, ' ', y2) end.

P-II-4 Kombinační sítě

Binární čísla můžeme sčítat po blocích pomocí sčítací sítě, která má na vstupech hodnoty obou bloků a přenos z nižšího řádu (tedy vlastně z předchozího bloku), na výstupu pak hodnotu součtu a přenos do vyššího řádu. Tato konstrukce ovšem vyžaduje, aby byl pro každý blok přenos z nižšího řádu k dispozici předem, což vede ke značnému zpomalení výpočtu. Rychlejšího výpočtu dosáhneme, budeme-li mít u každého bloku dvě sady výstupů: jednu pro případ, nedojde-li k přenosu z nižších řádů, druhou pro případ opačný. Blok tedy bude mít vstupy A0 až An-1 a B0 až Bn-1 a výstupy [M (přenos), X0 až Xn-1 (výsledek)] pro případ bez přenosu a [N, Y0 až Yn-1] pro případ s přenosem.

Tyto zobecněné blokové sčítačky je možné pro n=2k snadno konstruovat induktivně ze sčítaček menších. Pro n=1 získáme (s použitím již dříve zavedených hradel a hradla NXOR, jež je negací hradla XOR):
M = AND(A0, B0)
X0 = XOR(A0, B0)
N = OR(A0, B0)
Y0 = NXOR(A0, B0)
Ze sčítaček pro libovolné n pak sestrojíme sčítačku pro 2n: Vstupy rozdělíme do dvou skupin: A0 až An-1 + B0 až Bn-1 a An až A2n-1 + Bn až B2n-1. Každou skupinu pak sečteme již známou sčítačkou (výstupy první sčítačky budeme značit M1, X10 až X1n-1, N1, Y10 až Y1n-1, u druhé sčítačky pak s horním indexem 2). Výstupy sítě určíme podle následujících pravidel:

Síť lze tedy popsat takto (0 <= i < n):
Xi = X1i
Xi+n = SEL(X2i, Y2i, M1)
M = SEL(M2, N2, M1)
Yi = Y1i
Yi+n = SEL(X2i, Y2i, N1)
N = SEL(M2, N2, N1)
Tato struktura má dvě hladiny. První hladina obvodu bude realizovat 1-bitové sčítačky (viz výše), další dvě hladiny pak z dvojic výstupů 1-bitových sčítaček budou generovat součty 2-bitových skupin, další dvě hladiny 4-bitových atd. Celkem máme tedy O(log n) hladin.

Za výstup původní úlohy můžeme přímo prohlásit výstupy X0 až Xn-1 n-bitové sčítačky v nejnižší hladině, přičemž nejvyšším (n-tým) bitem výstupu je pak přenosový výstup M.