Ř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 A
0 až A
n-1 a
B
0 až B
n-1 a výstupy
[M (přenos), X
0 až X
n-1 (výsledek)] pro případ
bez přenosu a [N, Y
0 až Y
n-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:
- Sada výstupů pro případ bez přenosu: použijeme součet nižších
n bitů bez přenosu (tedy X10
až X1n-1}) a podle toho, zda M1
indikuje přenos do vyššího řádu, použijeme pro zbylé bity
a přenos do dalšího bloku buďto [M2,X2i] nebo [N2,X2i] (snadno
vybereme hradly SEL).
- Sada výstupů pro případ s přenosem: použijeme součet nižších
n bitů s přenosem (tedy Y10
až Y1n-1) a zvolíme výsledky týmž
způsobem, pouze místo M1 použijeme N1.
Síť lze tedy popsat takto (0 <= i < n):
X
i = X
1i
X
i+n = SEL(X
2i, Y
2i, M
1)
M = SEL(M
2, N
2, M
1)
Y
i = Y
1i
Y
i+n = SEL(X
2i, Y
2i, N
1)
N = SEL(M
2, N
2, N
1)
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.