Řešení úloh ústředního kola (1. soutěžní den) 51. ročníku
P-III-1
Nejdříve si zavedeme několik pojmů, které nám usnadní vyjadřování
při řešení této úlohy. Jestliže A je matice, pak A
i bude označovat
její i-tý sloupec.
Signatura prvku a
i,j matice A je
rovna hodnotě prvku a
i,j, pokud a
i,j je číslo.
Když a
i,j je žolík, pak jeho signaturou rozumíme nejmenší
číslo, které lze za žolík na pozici
a
i,j dosadit tak, aby i-tý řádek matice A tvořil neklesající
posloupnost. Pokud tedy a
i,j je žolík, pak jeho signatura je rovna
největšímu z čísel mezi prvky a
i,1,...,a
i,j-1; když mezi těmito
prvky není žádné číslo, je signatura a
i,j rovna nule. Signatura sloupce matice je
utříděná, jestliže
posloupnost signatur jeho prvků od prvního po poslední řádek je neklesající.
Po zbytek řešení je A pevně zadaná matice z naší úlohy.
Předpokládejme na chvíli, že máme dány sloupce A'1,...,A'k, které
jsou přerovnáním prvků ve sloupcích A1,...,Ak matice A.
Matici A* budeme nazývat rozšířením sloupců A'1,...,A'k,
pokud jsou splněny následující podmínky:
- matice A* má stejné rozměry jako matice A,
- i-tý sloupec matice A* je přerovnáním i-tého sloupce matice A,
- do matice A* lze za žolíky doplnit celá čísla tak, aby každý její řádek tvořil neklesající posloupnost a
- prvních k sloupců matice A* jsou sloupce A'1,...,A'k.
Navrhneme algoritmus, o kterém později ukážeme, že řeší naši úlohu.
Algoritmus bude postupně přerovnávat sloupce matice A od prvního
po poslední. Předpokládejme, že už jsme přerovnali prvních k sloupců
a že jsme tedy již nalezli A'
1,...,A'
k; navíc předpokládejme,
že signatura každého ze sloupců A'
1,...,A'
k je utříděná.
Popíšeme, jak přerovnáme další sloupec, tj. jak nalezneme
A'
k+1. Prvky sloupce A'
k+1 budeme volit v pořadí zdola nahoru:
Za prvek a'
i,k+1 zvolíme největší dosud nepoužité číslo ze sloupce
A
k+1, které je alespoň tak velké jako signatura prvku a'
i,k.
Pokud takové číslo neexistuje, zvolíme jako prvek a'
i,k+1 žolík.
Pokud již sloupec A
k+1 neobsahuje žádné nepoužité žolíky,
prohlásíme, že sloupce matice A nelze přerovnat. Povšimněte si,
že když jsme úspěšně vytvořili sloupec A'
k+1, pak jeho signatura
je utříděná.
Důkaz správnosti
Je jasné, že pokud se našemu algoritmu podařilo přerovnat všechny
sloupce matice A, potom výsledná matice je řešením úlohy. Zbývá
ukázat, že když náš algoritmus nenalezl přerovnání sloupců matice A,
pak žádné přerovnání sloupců matice A úlohu neřeší.
K tomu si nejprve dokážeme dvě pomocná tvrzení:
Tvrzení 1
Nechť A'
1,...,A'
k jsou přerovnání prvních k sloupců
matice A, jejichž signatury jsou utříděné. Nechť A'
k+1
je přerovnání (k+1)-ního sloupce matice A, které nalezl
náš algoritmus. Pokud existuje rozšíření sloupců A'
1,...,A'
k,
pak existuje i rozšíření sloupců A'
1,...,A'
k,A'
k+1.
Důkaz
Předpokládejme, že existuje rozšíření A
* sloupců
A'
1,...,A'
k. Pokud se (k+1)-ní sloupec A
* shoduje
s A'
k+1, pak tvrzení platí z triviálních důvodů.
Předpokládejme tedy, že sloupce A
*k+1 a A'
k+1 jsou
různé.
Nechť j je číslo nejspodnějšího řádku, kde se tyto sloupce liší.
Můžeme předpokládat, že A* je mezi všemi rozšířeními sloupců
A'1,...,A'k to, pro které je j nejmenší, tj. A*k+1
se liší od A'k+1 co nejvýše. Mohou nastat dva případy:
- a'j,k+1=* (a*j,k+1 je tedy číslo).
Potom ale náš algoritmus měl jako a'j,k+1 zvolit některé číslo
ze sloupce Ak+1: Číslo a*j,k+1 je totiž z triviálních
důvodů větší nebo rovno signatuře prvku aj,k a tedy, když
algoritmus volil prvek a'j,k+1, existovalo ve sloupci
Ak+1 nepoužité číslo, které bylo větší nebo rovno signatuře
prvku a'j,k.
- a'j,k+1 je číslo (a*j,k+1 je buď jiné číslo nebo žolík).
Sloupec A*k+1 obsahuje číslo a'j,k+1 na jiném než j-tém
řádku; buď i je číslo tohoto řádku. Platí tedy
a*i,k+1=a'j,k+1 a i<j.
Vyměňme nyní řádky i a j ve sloupcích k+1 až n v matici A*;
označme A** výslednou matici. Dokážeme, že A** je také
rozšíření A'1,...,A'k. Toto je ale ve sporu s volbou A*
jako rozšíření sloupců A'1,...,A'k takového, že se sloupce
A*k+1 a A'k+1 shodovaly na co nejvíce pozicích zdola.
Když dosadíme za prvky matice A* jejich signatury,
budou všechny řádky neklesající. Dosaďme ty samé hodnoty
za odpovídající žolíky v matici A** (tj. hodnoty z i-tého řádku
do j-tého a naopak). Jediné dvě dvojice prvků, kde by podmínka
monotonie mohla být po výměně porušena, jsou prvky v k-tém a
(k+1)-ním sloupci v i-tém nebo v j-tém řádku. Protože ale
sloupec A'k je utříděný, je signatura prvku a'i,k menší nebo
rovna signatuře prvku a'j,k a tedy i-tý řádek je neklesající.
Prvek a*i,k+1=a'j,k+1 je číslo a
signatura a*j,k = a**j,k je menší nebo rovna
číslu a*i,k+1=a**j,k+1.
Tedy i j-tý řádek je neklesající.
Tvrzení 2
Nechť jsou dána přerovnání A'
1,A'
2,...,A'
k prvních k sloupců
matice A a nechť je signatura sloupce A'
k utříděná.
Pokud se našemu algoritmu nepodaří vytvořit sloupec A'
k+1,
pak neexistuje rozšíření sloupců A'
1,A'
2,...,A'
k.
Důkaz
Označme j řádek, na kterém se náš algoritmus zastavil. Mezi
dosud nepoužitými prvky sloupce A
k+1 tedy nejsou již žádné žolíky a
všechna jeho čísla jsou menší než signatura a'
j,k. To ale
znamená, že sloupec A
k+1 obsahuje pouze m-j (m je počet řádků
matice A) žolíků a čísel, jež jsou větší nebo rovna signatuře prvku a'
j,k.
Pokud ale existuje rozšíření A
* sloupců A'
1,A'
2,...,A'
k,
pak všechny prvky a
*j,k+1,...,a
*m,k+1 jsou buď žolík nebo
čísla větší nebo rovna signatuře prvku a'
j,k (číslo a
*i,k+1
v i-tém řádku je větší nebo rovno signatuře a'
i,k a sloupec A'
k
je utříděný). Potom ale sloupec A
k obsahuje alespoň m-j+1
žolíků a čísel, která jsou větší nebo rovna signatuře prvku a'
j,k,
což jak víme není pravda.
Pomocí těchto dvou tvrzení již snadno dokážeme správnost našeho algoritmu.
Pokud pro 0 sloupců existuje rozšíření, pak podle Tvrzení 2 nalezne
náš algoritmus sloupec A'1 a pro něj též existuje rozšíření tentokrát
podle Tvrzení 1. Nyní podle Tvrzení 2 nalezne náš algoritmus sloupec A'2 a
pro sloupce A'1,A'2 existuje rozšíření podle Tvrzení 1, atd. Pokud tedy
existuje řešení, náš algoritmus ho nalezne.
Odhad časové a paměťové složitosti
Nechť vstupní matice A má n sloupců a m řádků. Na setřídění čísel
v každém z n sloupců potřebujeme čas O(m log m). Zbylé operace již
můžeme vykonat v čase O(m) (pro jeden sloupec). Celková časová složitost
algoritmu je tedy O(nm log m). Paměťová složitost je O(mn).
program P_III_1;
var a : array [1..100,1..100] of integer;
{ Matica A. Predpokladáme, že žolíky sú reprezentované ako -1 }
n, m : integer; { Rozmery matice A }
sig : array [1..100] of integer; { Signatúra posledného stĺpca }
stlpec : array [1..100] of integer; { Pomocné pole na jeden stĺpec }
procedure nacitaj;
var i, j : integer;
begin
readln(m, n); { načítaj rozmery }
for i := 1 to m do { načítaj maticu }
for j := 1 to n do
read(a[i,j]);
end; { nacitaj }
procedure tried(k : integer);
{ Utriedi k-ty stĺpec matice. Pre úsporu miesta použijeme
kvadratické triedenie, možno nahradiť n log n triedením.
Žolíky (reprezentované -1) budú navrchu. }
var i, j, min, pom : integer;
begin
for i := 1 to m-1 do begin
min := i; { nájdi minimum v neutriedenej časti stĺpca }
for j := i+1 to m do begin
if a[j,k] < a[min,k] then min := j;
end;
{ vymeň a[i,k] a a[min,k] }
pom := a[i,k]; a[i,k] := a[min,k]; a[min,k] := pom;
end;
end; { tried }
procedure vypis;
var i, j : integer;
begin
for i := 1 to m do begin
for j := 1 to n do
write(' ',a[i][j]);
writeln; { ukonči riadok i }
end;
end;
var i, k, pouzi : integer;
begin { hlavný program }
nacitaj; { vstup }
for i := 1 to m do sig[i] := 0; { inicializuj signatúru }
for k := 1 to n do begin { pre všetky stĺpce }
tried(k); { utrieď stĺpec }
pouzi := m; { posledné nepoužité číslo }
{ ukladaj čísla odspodu do pomocného poľa "stlpec" }
for i := m downto 1 do begin
if a[pouzi][k] >= sig[i] then begin
stlpec[i] := a[pouzi][k];
pouzi := pouzi-1;
end
else stlpec[i] := -1; { ak sa nedá použiť číslo, použi žolík }
end;
{ ak zostali nepoužité čísla, nemožno usporiadať }
if (pouzi >= 1) and (a[pouzi][k] <> -1) then begin
writeln('Maticu nemozno usporiadat');
exit;
end;
{ skopíruj pomocné pole späť do matice a prepočítaj signatúru }
for i := 1 to m do begin
a[i][k] := stlpec[i];
if stlpec[i] <> -1 then sig[i] := stlpec[i]
end;
end;
vypis; { výpis matice }
end.
P-III-2
Úlohu budeme řešit pomocí dynamického programování.
Trasu, která splňuje všechny podmínky kladené na vyhovující trasy s výjimkou
podmínky, že musí končit v nejníže položeném orientačním bodě,
budeme nazývat
částečná trasa. Náš program bude počítat
počet částečných tras, které končí v jednotlivých orientačních bodech.
Nejdříve si popíšeme algoritmus, který pracuje v čase O(N3),
kde N je počet orientačních bodů. Utřídíme orientační
body sestupně podle jejich nadmořské výšky a očíslujeme je v získaném
pořadí od 1 do N. Pro i,j (1<=i<j<=N) bude hodnota a[i,j] určovat
počet částečných tras, které mají i jako předposlední orientační bod a
končí v bodě j. Pro i=1 bude a[i,j]=1, protože trasa z orientačního
bodu 1 do orientačního bodu j je právě jedna. Předpokládejme, že jsme
již spočítali hodnoty a[i',j'] pro j'<j a chceme spočítat hodnoty a[i,j]
pro 1<=i<=N. Pokud má uvažovaná částečná trasa končit úsekem i,j,
musí do bodu i přijít z bodu k (s nadmořskou výškou větší než je výška
bodu i) takového, že úhel otočení ze směru ki do směru ij
je nejvýše 45o. Označme S(i,j) množinu všech takových bodů k.
Potom hodnota a[i,j] je rovna součtu a[k,i] přes všechna k z S(i,j).
Algoritmus pracující v kubickém čase lze nyní již snadno sestrojit.
Úvodní setřídění orientačních bodů dle nadmořských výšek lze provést v čase
O(N log N). Hodnoty a[i,j]
budeme počítat podle rostoucí hodnoty indexu i. Pro každou z O(N2)
dvojic i a j existuje pouze O(N) čísel k - otestování, zda
k je v S(i,j), provedeme pomocí funkce uhel ze zadání úlohy.
Počet hledaných tras pak určíme jako součet
hodnot a[j,N] přes všechna j, 1<=j<N. Náš algoritmus zjevně
pracuje v čase O(N3) a v prostoru O(N2).
Právě sestrojený algoritmus ještě dále zrychlíme pomocí podobného
triku, jaký jsme použili již v minulých kolech.
Pro bod i setřídíme body k, k<i, podle směrů ki ve směru
hodinových ručiček, a též body j, j>i, podle směrů ij.
Pro každé j>i, je množina S(i,j) tvořena souvislým úsekem
bodů k, k<i, v právě zavedeném uspořádání - nechť l(i,j) a p(i,j)
jsou krajní body tohoto souvislého úseku (předpokládejme, že je neprázdný).
Pro pevný bod i budeme k a[i,j] přičítat součet hodnot
od a[l(i,j),i] do a[p(i,j),i], kde j (j>i) budeme procházet
v pořadí podle výše uvedeného uspořádání. Jak se směr ij postupně
natáčí, hodnoty l(i,j) a p(i,j) se postupně mění (ale stále stejným
směrem). Hodnotu součtu prvků mezi a[l(i,j),i] a a[p(i,j),i] si můžeme
pamatovat v pomocné proměnné a při změně l(i,j) nebo p(i,j) ji patřičně
upravit. Na výpočet v pevném bodě i
takto budeme potřebovat kromě úvodního třídění čas O(N).
Třídění podle směrů (úhlů) spotřebuje v každém z N bodů
čas O(Nlog N). Výsledná časová složitost našeho algoritmu tedy bude
O(N2log N) a paměťová bude O(N2).
Při implementaci algoritmu je třeba dávat pozor na několik okrajových
případů, zejména na již výše zmiňovaný případ, že množina S(i,j)
je prázdná. Kvůli úspoře místa bylo ve vzorovém programu použito
kvadratického třídícího algoritmu namísto optimálního algoritmu
pracujícího v čase O(N log N).
program P_III_2;
const MAX_N = 100;
var N : integer; { počet bodov }
x,y : array[1..MAX_N] of real; { súradnice bodov }
pocet : array[1..MAX_N,1..MAX_N] of integer;
{ počet čiastočných trás s danou poslednou hranou }
ind : array[1..MAX_N] of integer;
{ indexové pole na triedenie podľa uhla }
uhol_ind : array[1..MAX_N] of real;
{ uhol zodpovedajúci bodu v ind[i] }
function uhol(x, y : real) : real;
var vysl : real;
begin { implementácia funkcie "uhol" definovanej v zadaní }
if x = 0 then begin { špeciálny prípad x=0 }
if y > 0 then uhol := 90
else uhol := 270;
end
else begin { x<>0, môžeme použit arctan }
vysl := arctan(y/x) / pi * 180;
if x < 0 then vysl := vysl - 180; { zmeň výsledok podľa kvadrantu }
if vysl < 0 then vysl := vysl + 360;
uhol := vysl;
end;
end; { uhol }
procedure tried(stred : integer);
var pom_r : real;
var i, j, min, pom_i : integer;
begin { utriedi body okolo bodu "stred", ich indexy uloží
do pola "ind" a uhly do pola "uhol_ind". }
{ inicializuj ind a spočítaj uhly }
j := 1;
for i := 1 to N do begin
if i<>stred then begin { bod "stred" vynechaj }
ind[j] := i;
uhol_ind[j] := uhol(x[i] - x[stred], y[i] - y[stred]);
j := j+1;
end;
end;
{ tried ind podla uhol_ind }
for i := 1 to N-1 do begin
min := i; { nájdi minimum v neutriedenej časti pola }
for j := i+1 to N-1 do begin
if uhol_ind[j] < uhol_ind[min] then min := j;
end;
{ ulož minimum do ind[i] }
pom_i := ind[i]; ind[i] := ind[min]; ind[min] := pom_i;
pom_r := uhol_ind[i]; uhol_ind[i] := uhol_ind[min];
uhol_ind[min] := pom_r;
end;
end; { tried }
procedure spocitaj_z_bodu(stred : integer);
var zac, kon, sucet, i : integer;
uhol_zac, uhol_kon : real;
begin { spočítaj pocet[stred,i] pre všetky i>stred }
tried(stred);
zac := 1; { prvý bod, ktorý je aspoň na začiatku výseku }
kon := 1; { prvý bod, ktorý je za koncom výseku }
sucet := 0; { súčet bodov vo výseku }
for i := stred to N-1 do begin
uhol_zac := uhol_ind[i] - 180 - 45; { spočítaj výsek }
uhol_kon := uhol_ind[i] - 180 + 45;
if uhol_kon > 180 then uhol_kon := 180;
{ posuň indexy "zac" a "kon", udržuj "sucet" }
while uhol_ind[zac] < uhol_zac do begin
sucet := sucet - pocet[ind[zac], stred];
zac := zac+1;
end;
while uhol_ind[kon] <= uhol_kon do begin
sucet := sucet + pocet[ind[kon], stred];
kon := kon+1;
end;
pocet[stred, ind[i]] := sucet; {ulož výsledok}
end;
end; { spocitaj_z_bodu }
procedure inicializuj;
var i, j : integer;
pom : real;
begin { načítaj vstup a strieď podľa y zhora nadol }
read(N);
for i := 1 to N do begin
read(x[i], y[i]);
j := i; { vlož nový bod na správne miesto }
while (j > 1) and (y[j] >= y[j-1]) do begin
pom := x[j-1]; x[j-1] := x[j]; x[j]:=pom;
pom := y[j-1]; y[j-1] := y[j]; y[j]:=pom;
j := j-1;
end;
end;
end; { inicializuj }
var i, sucet : integer;
begin { hlavný program }
inicializuj; { načítanie a utriedenie podľa y }
for i := 2 to N do pocet[1, i] := 1;
for i := 2 to N-1 do spocitaj_z_bodu(i);
sucet := 0; { sčítaj hodnoty pocet[i,N] }
for i := 1 to N-1 do sucet := sucet + pocet[i, N];
writeln(sucet); { vypíš výsledok }
end.
P-III-3
Nejdříve si předvedeme jednodušší řešení, které pro každou permutaci
vytvoří síť s O(log n) vrstvami a O(n log n) komparátory.
Později toto řešení vylepšíme, aby používalo pouze O(n) komparátorů.
Časová složitost obou algoritmů bude O(n log n).
Nechť permutace na vstupu je A=a1,a2,... an a zvolme
k:=[n/2] ([x] je dolní celá část čísla x).
Po průchodu první vrstvou budou na prvních k vodičích
čísla 1,2,...,k (ne nutně setříděná) a na zbylých n-k vodičích
čísla k+1,k+2,...,n (opět ne nutně setříděná). První vrstva
bude vypadat následovně: Nechť S1 je množina vodičů z horní poloviny,
na kterých jsou čísla z dolní poloviny, tj. S1={i|i<=k & ai>k}.
Podobně S2 bude množina vodičů patřících do dolní poloviny, na kterých
jsou čísla z horní poloviny, tj. S2={i|i>k & ai<=k}.
Zřejmě |S1|=|S2|. Pomocí komparátorů spojíme dvojice vodičů, z nichž
vždy jeden je z množiny S1 a druhý S2. Takto vytvoříme první vrstvu
sítě a je zřejmé, že tato vrstva má požadovanou vlastnost.
Nyní rozdělíme n vodičů na dvě skupiny: horních k vodičů a dolních
n-k vodičů. Právě popsaný postup zopakujeme na každé z těchto dvou
skupin zvlášť a takto vytvoříme druhou vrstvu. Na vodičích z každé
čtvrtiny budou čísla z této čtvrtiny. Takto budeme pokračovat, dokud v každé
části, na které máme vodiče rozděleny, nezbude jediný vodič. Počet vrstev
takto vytvořené sítě bude O(log n) (velikosti částí se zmenší v každé
vrstvě na polovinu) a počet komparátorů této sítě bude O(nlog n).
Dále si popíšeme konstrukci s O(n) komparátory. Ta funguje podobně,
ale dvojice vodičů z množin S1 a S2 vybereme šikovnějším způsobem.
Permutaci si můžeme představit jako orientovaný graf na vrcholech
1,...,n, kde z vrcholu i vede právě jedna hrana, a to do vrcholu
ai. Zjevně z každého vrcholu vychází právě jedna hrana a právě jedna
hrana do něj vchází. Cykly v takto vytvořeném grafu budeme nazývat
cykly permutace. Např. permutace (7,5,4,1,2,6,8,3) má 3 cykly:
(1->7->8->3->4->1), (2->5->2), (6->6).
V naší komparátorové síti bychom chtěli přesunout číslo z vodiče i
na vodič ai. Protože čísla i a ai jsou ve stejném cyklu, je
zbytečné pomocí komparátorů spojovat vodiče z různých cyklů permutace A.
Na začátku v lineárním čase proto rozdělíme permutaci na její cykly a
v každém z nich budeme řešit úlohu samostatně. Může se ale samozřejmě
stát, že permutace je tvořena jen jedním cyklem a tímto dělením
na menší úlohy si tedy nepomůžeme.
Zvolme jeden pevný cyklus
(x1->x2->...->xl->x1)
permutace A a nechť k:=[l/2] (k bude mít opět roli
"poloviny" délky cyklu). Nejmenších k čísel tohoto cyklu
budeme nadále nazývat malá čísla a zbylých n-k čísel
budeme nazývat velká čísla. Např. pro cyklus
(1->7->8->3->4->1)
je k=2, čísla 1 a 3 jsou malá a čísla 4, 7 a 8 jsou velká.
Podívejme se na souvislé úseky velkých a malých čísel v našem cyklu;
souvislý úsek může pokračovat i z xl do x1.
Nechť xi je poslední číslo v některém z úseků velkých čísel;
za xi tedy následuje úsek malých čísel a nechť xj je poslední
číslo v tomto úseku.
Vodič xi obsahuje číslo ax_i, které je malé, a naopak
vodič xj obsahuje číslo ax_j, které je velké. Kdybychom spojili
xi-tý a xj-tý vodič komparátorem, dojde k výměně, protože vodič
s malým číslem xi obsahuje velké číslo ax_i a naopak vodič
s velkým číslem xj obsahuje malé číslo ax_j.
Pro každý souvislý úsek velkých čísel takto vytvoříme komparátor,
který spojí vodič odpovídající poslednímu číslu tohoto úseku
s vodičem, který odpovídá poslednímu číslu následujícího úseku
malých čísel. V našem příkladu
(1->7->8->3->4->1)
čísla 7 a 8 tvoří první souvislý úsek velkých čísel a 3
následující úsek malých čísel. Do sítě tedy přidáme komparátor mezi vodiče
8 a 3. Další souvislý úsek velkých čísel je tvořen číslem 4 a
úsek malých čísel pouze číslem 1. Do naší sítě tedy přidáme komparátor
mezi vodiče 1 a 4.
Takto vytvoříme komparátory první vrstvy. Po průchodu první vrstvou se
původní velký cyklus rozpadne na několik menších. Každý souvislý úsek
malých čísel bude tvořit samostatný cyklus, naopak všechna velká čísla
budou obsažena v jednom cyklu (nakreslete si obrázek!).
Pokud jsme použili p komparátorů, vytvoříme z původního jednoho cyklu
p+1 nových cyklů. Nyní obdobným postupem nalezneme cykly permutace
po průchodu prvním cyklem a vytvoříme druhou vrstvu. Skončíme, když všechny
cykly jsou jednoprvkové. Protože každý komparátor "přidá" jeden cyklus,
bude mít výsledná síť nejvýše n-1 komparátorů. Každá vrstva zmenší
velikost největšího cyklu zhruba na polovinu, počet vrstev je proto
logaritmický v n.
Výše popsaný algoritmus může každou z O(log n) vrstev vytvořit
v čase O(n): Nejdříve v čase O(n) rozložíme permutaci na cykly.
To lze udělat tak, že si vytvoříme pomocné pole velikosti n,
které na začátku vynulujeme. Vezmeme nejmenší číslo i takové, že i-tý
prvek tohoto pole je stále nulový, a nalezneme jeho cyklus, tj. procházíme
posloupnost i, ai, a_a_i atd., dokud se nevrátíme zpět do i.
Všem číslům této posloupnosti uložíme do pomocného pole číslo i.
Na konci bude pomocné pole obsahovat pro každý prvek číslo nejmenšího
prvku v jeho cyklu. Když jsme nalezly všechny cykly, spočítáme si jejich
velikosti a rozdělíme čísla v nich na velká a malá. Tu je třeba postupovat
opatrně - musíme totiž (rychle) určit hranici, která oddělí velká a malá čísla
v jednom cyklu. Jednou z možností je použít lineární algoritmus na hledání
mediánu. Jednodušší řešení je následující: Budeme procházet naše pomocné
pole od nejmenšího indexu k největšímu - u každého cyklu budeme jeho čísla
označovat jako malá, dokud nenavštívíme polovinu jeho prvků (pro každý cyklus
máme zvláštní čítač, kolik jeho prvků jsme již navštívili) a pak prvky tohoto
cyklu budeme označovat jako velká. Tento průchod, na který spotřebujeme čas
O(n), nám naráz rozdělí čísla ve všech cyklech na velká a malá. Po vytvoření
nové vrstvy nesmíme zapomenout spočítat, jak se nám změnila naše permutace
po průchodu touto vrstvou.
program P_III_3;
const MAX=1000;
var a, nove_a, cyklus, velkost, najdene : array[1..MAX] of integer;
cast : array[1..MAX] of char;
n : integer;
i, j, pocet_cyklov, velkost_cyklu : integer;
hotovo : boolean;
begin
{načítaj dáta}
readln(n);
for i := 1 to n do read(a[i]);
{vypisuj jednotlivé vrstvy}
hotovo := false;
while not hotovo do begin { pre každú vrstvu }
{nájdi cykly a ich veľkosti}
for i := 1 to n do cyklus[i] := 0;
pocet_cyklov := 0;
for i := 1 to n do begin
if cyklus[i]=0 then begin {nový cyklus}
j := i;
inc(pocet_cyklov);
velkost_cyklu := 0;
while cyklus[j] = 0 do begin
cyklus[j] := pocet_cyklov;
j := a[j];
inc(velkost_cyklu);
end; {while}
velkost[pocet_cyklov] := velkost_cyklu;
end; {if}
end; {for i}
{označ prvky cyklov ako + a -}
for i := 1 to pocet_cyklov do najdene[i] := 0;
for i := 1 to n do begin
inc(najdene[cyklus[i]]);
if najdene[cyklus[i]] <= velkost[cyklus[i]] div 2 then
cast[i] := '-'
else
cast[i] := '+';
end; {for i}
{ skončili sme, ak máme n cyklov }
if pocet_cyklov = n then hotovo := true
else begin
{ nájdi komparátory a zapíš nové hodnoty poľa a }
nove_a := a;
for i := 1 to n do begin
if (cast[i] = '+') and (cast[a[i]] = '-') then begin
j := a[i]; {nájdi koniec úseku mínusov}
while cast[a[j]] = '-' do j := a[j];
writeln('Komparator (', i, ',', j, ')');
nove_a[i] := a[j]; {výmena spôsobená komparátorom}
nove_a[j] := a[i];
end;
end;
a := nove_a;
writeln('Koniec vrstvy');
end; {else}
end; {while}
end.