Řešení úloh ústředního kola (2. soutěžní den) 51. ročníku
P-III-4
Úlohu si nejdříve přeformulujeme do řeči teorie grafů. Uzly kanalizační
sítě budeme nazývat
vrcholy, potrubí vedoucí mezi nimi
hrany a
celá kanalizační síť pak pro nás bude
graf.
Sledem budeme
rozumět posloupnost ne nutně různých vrcholů a hran
v
0,e
1,v
1,e
2,...,v
k-1e
k,v
k
takovou, že hrana e
i spojuje
vrcholy v
i-1 a v
i. Sled nazveme
tahem, pokud se v něm žádná
hrana nevyskytuje dvakrát.
Naše úloha tedy požaduje nalézt v zadaném grafu G nejmenší množinu
tahů takovou, že každá hrana je obsažena v právě jednom z nich.
Pokud si představíme náš graf G jako obrázek, chceme ho nakreslit
co nejmenším počtem tahů.
Nejdříve si uvědomíme několik jednoduchých skutečností.
Pokud je graf nesouvislý, můžeme úlohu řešit pro každou
jeho komponentu souvislosti zvlášť. Připomeňme si, že komponenta souvislosti
grafu je maximální množina vrcholů taková, že mezi každými dvěma z nich vede sled.
Graf je souvislý, pokud je tvořen jedinou komponentou souvislosti.
Nadále tedy stačí řešit případ, že zadaný graf je souvislý.
Stupeň vrcholu grafu je počet hran, které z něho vycházejí.
Součet stupňů všech vrcholů grafu je sudý, neboť každá hrana tento součet
zvýší o dva (u každého ze svých dvou konců o jedna).
Protože součet stupňů všech vrcholů je sudý, má každý graf sudý počet
vrcholů lichého stupně. Nechť tedy náš graf má 2k vrcholů lichého
stupně.
V každém z těchto 2k vrcholů alespoň jeden z hledaných tahů končí nebo
začíná. Nechť w je vrchol lichého stupně, kde žádný tah ani nezačíná,
ani nekončí. Každý tah musí obsahovat sudý (třeba i nulový) počet
hran vycházejících z vrcholu w a protože všechny tahy dohromady obsahují
každou hranu grafu právě jednou, musí být stupeň vrcholu w sudý, což není.
Potom ale libovolné řešení musí obsahovat alespoň k tahů (pro k=0
alespoň jeden tah).
Nejprve vyřešíme případ, že všechny vrcholy grafu mají sudé stupně,
tj. k=0. Obecný případ s nenulovým k vyřešíme později.
Pro k=0 dokážeme, že existuje uzavřený tah obsahující všechny hrany.
Připomeňme si, že tah je uzavřený, pokud začíná a končí ve stejném vrcholu.
Vezměme nejdelší tah v našem grafu, tj. ten, co obsahuje co nejvíce hran.
Takový tah je zřejmě uzavřený: Kdyby nebyl, pak by z jeho posledního vrcholu,
označme ho w, vycházel lichý počet hran obsažených v našem tahu, ale protože
stupeň w je sudý, existovala by i nepoužitá hrana vycházející z vrcholu w a
náš tah by šel prodloužit. Tedy nejdelší tah je nutně uzavřený. Pokud tento
tah neobsahuje všechny hrany, pak existuje vrchol w, ze kterého vychází jak hrana,
která je obsažena v našem tahu, tak i hrana, která není v našem tahu (uvědomme si, že
graf je souvislý). Protože náš tah je uzavřený, můžeme předpokládat,
že w je jeho první a zároveň poslední vrchol a tento tah lze potom prodloužit přidáním,
nepoužité hrany, která vede z vrcholu w. Právě jsme tedy ukázali,
že nejdelší tah v souvislém grafu, jehož všechny stupně jsou sudé, obsahuje
každou hranu právě jednou (jinak by šel prodloužit).
Zpět k našemu problému: Jak nakreslit souvislý graf s 2k vrcholy
lichého stupně pomocí k tahů? Přidejme do našeho grafu k hran, které
budou spojovat dvojice vrcholů lichého stupně. Takto vytvořený graf
je souvislý a všechny jeho vrcholy mají sudé stupně. Existuje v něm
tedy tah, který obsahuje každou hranu právě jednou. Pokud z tohoto
tahu vynecháme k přidaných hran, pak se nám rozpadne na k tahů -
sestrojili jsme tedy hledaných k tahů.
Zbývá vyřešit jediný úkol -- efektivně nalézt uzavřený tah v grafu
jehož všechny stupně jsou sudé. Zbývající operace, tj. rozložit graf
na komponenty souvislosti a přidat hrany mezi vrcholy lichého
stupně, jistě zvládneme v lineárním čase v počtu vrcholů a hran.
Algoritmus bude postupně přidávat hrany do vytvářeného tahu
v grafu; jeho jádrem bude rekurzivní procedura
vytvor_tah. Začneme vytvářet tah ve vrcholu v, dokud nepřijdeme
do vrcholu, z něhož už nevede žádná nepoužitá hrana. Protože stupně
všech vrcholů jsou sudé, musí být tímto vrcholem opět vrchol v.
Máme tedy nějaký uzavřený tah. Pokud existuje vrchol u,
jehož všechny hrany jsme ještě nepoužili, zavoláme pro něj
proceduru vytvor_tah. Takto nalezneme tah, který prochází
vrcholem u a obsahuje pouze dosud nepoužité hrany.
Vrchol u nyní nemá žádné nepoužité hrany a
nově nalezený tah spojíme s původním tahem. Takto pokračujeme,
dokud existuje vrchol u, jehož některá hrana je nepoužitá.
Nyní k samotné implementaci výše popsaného algoritmu.
V programu budeme mít pro každý vrchol uložen seznam jeho hran a ukazatel
do tohoto seznamu na takovou hranu, že všechny hrany před ní jsou
již použité. Pokud budeme potřebovat najít dosud nepoužitou hranu,
budeme tento ukazatel posunovat v seznamu, dokud takovou
hranu nenalezneme. Pokud jsou všechny hrany použité, ukazatel se
posune až na konec seznamu. Takto u každého vrcholu spotřebujeme
dohromady čas úměrný jeho stupni a tedy celkově čas O(m) pro všechny
vrcholy dohromady.
Samotné tahy budeme reprezentovat jako seznamy hran - to nám umožní
tahy nejen rychle vytvářet, ale i spojovat. Náš algoritmus tedy
nejdříve nalezne počáteční tah, např. z prvního vrcholu. Potom budeme
procházet vrcholy na tomto tahu, dokud nenarazíme na první vrchol
s nějakou dosud nepoužitou hranou. Zavoláme na tento vrchol
proceduru vytvor_tah a spojíme tah, který tato procedura
nalezne, s původním tahem. Všimněte si,
že při vhodné implementaci procedury vytvor_tah nebude
již třeba pro vrcholy na přidávaném tahu kontrolovat, zda jsou
všechny jejich hrany použity (pokud to zkontroluje sama
volaná procedura vytvor_tah). Celková časová a paměťová
složitost našeho
algoritmu tedy bude O(m), kde m je počet hran.
Kvůli zjednodušení vzorového programu náš program nespojuje vrcholy
lichého stupně jen v rámci jedné komponenty - to ale zřejmě nebude mít
vliv na počet nalezených tahů.
program P_III_4;
const MAXN = 201; MAXM = MAXN * MAXN + MAXN;
type
hrana = record { typ: hrana }
zac, kon : integer; { začiatočný a koncový vrchol }
pridana : boolean; { je to jedna z umelo pridaných hrán? }
pouzita : boolean; { je hrana použitá v ťahu? }
dalsia : integer; { ďalšia hrana v ťahu }
end;
zoznam_sm = ^ zoznam; { typ: smerník na prvok zoznamu hrán }
zoznam = record { typ: prvok zoznamu hrán }
hrana : integer; { číslo hrany }
dalsia : zoznam_sm; { smerník na ďalší prvok zoznamu }
end;
var hrany : array[1..MAXM] of hrana; { pole hrán }
susedia : array[1..MAXN] of zoznam_sm; { zoznam hrán pre každý vrchol }
stupen : array[1..MAXN] of integer; { stupeň vrchola }
nepouzite : array[1..MAXN] of zoznam_sm;
{ prvá hrana v zozname, ktorá môže byť nepoužitá }
zaciatky : array[1..MAXN] of integer; { začiatky ťahov }
pocet_zac : integer; { počet začiatkov v poli zaciatky }
n, m : integer; { počet hrán a vrcholov }
procedure pridaj_suseda(komu, hrana : integer);
var zvysok : zoznam_sm;
begin { pridaj hranu "hrana" do zoznamu pre vrchol "komu" }
zvysok := susedia[komu]; { odlož si zvyšok zoznamu }
new(susedia[komu]); { vytvor nový prvok }
susedia[komu]^.hrana := hrana;
susedia[komu]^.dalsia := zvysok;
inc(stupen[komu]); { zvýš stupeň vrcholu }
end; { pridaj_suseda }
procedure pridaj_hranu(index, zac, kon : integer; pridana : boolean);
begin { pridaj novú hranu na pozíciu "index" }
hrany[index].zac := zac; hrany[index].kon := kon;
hrany[index].dalsia := 0;
hrany[index].pouzita := false;
hrany[index].pridana := pridana;
pridaj_suseda(zac, index); { pridaj do zoznamov pre oba koncové vrcholy }
pridaj_suseda(kon, index);
end; { pridaj_hranu }
procedure nacitaj;
var i, zac, kon : integer;
begin { načítaj vstup a inicializuj polia }
readln(n,m);
for i := 1 to n do begin
susedia[i] := nil;
stupen[i] := 0;
end;
for i := 1 to m do begin
readln(zac, kon);
pridaj_hranu(i, zac, kon, false);
end;
end; { nacitaj }
function nepouzita_hrana(vrchol : integer) : integer;
{ Vráti prvú nepoužitú hranu z vrcholu alebo 0, ak neexistuje.
V "nepouzite[vrchol]" si uložíme hrany, ktoré už sme prehľadali
(kvôli zrýchleniu ďalšieho prehľadávania). }
var p : zoznam_sm;
nasiel : boolean;
begin
p := nepouzite[vrchol];
nasiel := false;
while (p <> nil) and not nasiel do begin { preskoč použité hrany }
if not hrany[p^.hrana].pouzita then nasiel := true
else p := p^.dalsia;
end;
nepouzite[vrchol] := p; { ulož si preskočené hrany }
{ našli sme nepoužitú hranu ? }
if nasiel then nepouzita_hrana := p^.hrana
else nepouzita_hrana := 0;
end; { nepouzita_hrana }
function druhy_koniec(hrana, koniec : integer) : integer;
begin { vráť ten koniec hrany, ktorý nie je rovný "koniec". }
if hrany[hrana].zac = koniec then
druhy_koniec := hrany[hrana].kon
else
druhy_koniec := hrany[hrana].zac;
end; { druhy_koniec }
procedure zorientuj_hranu(hrana, koniec : integer);
begin { otoč hranu tak, aby mala koniec v "koniec" }
if hrany[hrana].zac = koniec then begin
hrany[hrana].zac := hrany[hrana].kon;
hrany[hrana].kon := koniec;
end;
end;
procedure vytvor_tah(vrchol : integer;
var prva_hrana, posledna_hrana : integer;
var bola_pridana : boolean);
{ Rekurzívne vytvor uzavretý ťah začínajúci vo "vrchol" taký,
že každý vrchol na ňom má použité všetky hrany. Vráť prvú
a poslednú hranu a tiež či sme pridali aspoň jednu pridanú hranu. }
var akt, hrana, dalsia_hrana, nova_prva, nova_posledna : integer;
nova_bola : boolean;
begin
bola_pridana := false;
{ nájdi cyklus začínajúci vo vrchole "vrchol" }
akt := vrchol; { aktuálny vrchol }
hrana := nepouzita_hrana(akt);
prva_hrana := hrana;
while hrana<>0 do begin { kým vieme cyklus predĺžiť, predĺžme }
posledna_hrana := hrana;
hrany[hrana].pouzita := true;
akt := druhy_koniec(hrana, akt);
hrana := nepouzita_hrana(akt);
hrany[posledna_hrana].dalsia := hrana;
zorientuj_hranu(posledna_hrana,akt);
end;
{ prejdi cyklus znova a doplň ďalšie cykly, kde chýbajú }
hrana := prva_hrana;
akt := vrchol;
while hrana<>0 do begin
if hrany[hrana].pridana then bola_pridana := true;
dalsia_hrana := hrany[hrana].dalsia;
if nepouzita_hrana(akt)<>0 then begin { ešte je čo pridať }
vytvor_tah(akt, nova_prva, nova_posledna, nova_bola);
if nova_bola then bola_pridana := true;
hrany[hrana].dalsia := nova_prva;
hrany[nova_posledna].dalsia := dalsia_hrana;
end;
akt := druhy_koniec(hrana, akt);
hrana := dalsia_hrana;
end;
{ zacyklíme nájdený cyklus }
hrany[posledna_hrana].dalsia := prva_hrana;
end;
procedure pridaj_hrany;
var i, posledny : integer;
begin { pridaj hrany medyi vrcholmi nepárneho stupňa }
pocet_zac := 0;
posledny := 0; { číslo posledného nepárneho nespárovaného vrcholu }
for i := 1 to n do begin
if stupen[i] mod 2 = 1 then begin
if posledny = 0 then posledny := i
else begin
inc(m);
pridaj_hranu(m, posledny, i, true);
inc(pocet_zac);
zaciatky[pocet_zac]:=m;
posledny := 0;
end; {else}
end; {if stupen}
end; {for i}
end;
procedure vypis_tah(zmazana_hrana : integer);
var hrana : integer;
begin { vypíš tah pokračujúci za hranou "zmazana_hrana" }
hrana := hrany[zmazana_hrana].dalsia; { prvá hrana, ktorú vypíšeme }
while (hrana<>zmazana_hrana) and (not hrany[hrana].pridana) do begin
write(hrany[hrana].zac,' ');
hrana := hrany[hrana].dalsia;
end;
write(hrany[hrana].zac); { vypíš druhý koniec posledne vypísanej hrany }
if not hrany[hrana].pridana then { ak sme v komponente bez pridanej hrany }
writeln(' ',hrany[hrana].kon) { vypíšeme ešte jeden vrchol }
else
writeln;
end;
var i, prva_hrana, posledna_hrana : integer;
bola_pridana : boolean;
begin { Hlavný program }
nacitaj; { vstup a inicializácia }
pridaj_hrany; { pridanie hrán, aby stupňe boli párne }
for i := 1 to n do nepouzite[i] := susedia[i]; { inicializuj "nepouzite" }
{ pre každý vrchol, ktorý má neprejdené hrany prejdi komponent }
for i := 1 to n do begin
if nepouzita_hrana(i)<>0 then begin
vytvor_tah(i, prva_hrana, posledna_hrana, bola_pridana);
if not bola_pridana then begin { párny komponent pridaj do začiatkov }
inc(pocet_zac);
zaciatky[pocet_zac] := prva_hrana;
end;
end;
end;
{ výpis výsledku }
writeln(pocet_zac);
for i := 1 to pocet_zac do begin
vypis_tah(zaciatky[i]);
end;
end.
P-III-5
Myšlenka řešení této úlohy je velmi jednoduchá. Vygenerujeme postupně
všechny pozice s nejvýše N kameny, ze kterých se dá cílová pozice
dosáhnout. Budeme si pamatovat všechny již vygenerované pozice a kdykoliv
vygenerujeme nějakou další, nejdříve si zkontrolujeme, zda již mezi dříve
vytvořenými pozicemi náhodou není. Není-li tomu tak,
zapamatujeme si ji a zvýšíme počítadlo vyhrávajících pozic s nejvýše N
kameny o jedničku.
Pozice budeme generovat v pořadí od cílové pozice. Pokud posledním tahem
byl skok doprava z políčka i na políčko i+2, pak jsou nyní políčka
i a i+1 prázdná a naopak políčko i+2 obsahuje hrací kámen.
Pozice, ze kterých se dá dostat do pozice p skokem doprava,
jsou právě ty, které vzniknou záměnou řetězce 001 v popisu
pozice p řetězcem 110 (představujeme si, že pozice je popsána
posloupností nul a jedniček, kde nula reprezentuje prázdné políčko a
jednička reprezentuje obsazené políčko). Podobně ty pozice, ze kterých
se dá dostat do p skokem doleva, jsou právě ty, které vzniknou záměnou
řetězce 100 řetězcem 011.
Výše popsaným postupem můžeme tedy pro pozici p vygenerovat všechny
pozice, ze kterých se lze do p dostat jedním tahem. Popíšeme si
proceduru generuj, která pro zadanou pozici p vygeneruje
všechny pozice, ze kterých se dá do pozice p dostat. Výše uvedeným
postupem tato procedura bude vytvářet pozice q, z nichž se dá přejít
do p jedním tahem. Pokud q ještě nebyla nalezena, označíme q
jako nalezenou a rekurzivně na ni zavoláme proceduru generuj.
Potřebujeme umět rychle ověřovat, zda již pozice q byla někdy dříve
vygenerována. Vhodných datových struktur je několik, např. hašovací tabulky,
různé varianty vyhledávacích stromů atd. My použijeme datovou
strukturu nazývanou trie.
Trie je datová struktura na uchovávání řetězců nad konečnou abecedou,
v našem případě to budou řetězce nul a jedniček. Trie je tvořena stromem,
kde každý vrchol má nejvýše tolik synů, jaká je velikost abecedy,
tzn. v našem případě nejvýše dva syny. Cesty od kořene stromu odpovídají
řetězcům nad abecedou. V našem případě to bude tak, že pokud i-tá
hrana cesty vede do levého syna, je i-tý znak řetězce 0, a pokud
vede do pravého syna je tento znak 1. Každý vrchol w ve stromě
obsahuje ukazatele na své syny (pokud nějaké má) a jeden bit udávající,
zda řetězec, kterému tento vrchol odpovídá, byl do trie vložen či nikoliv. Na začátku je
trie tvořena pouze kořenem, jehož bit je nastaven na nulu. Slovo do trie
vložíme tak, že jdeme po hranách odpovídajících znakům vkládaného slova a
pokud už nemůžeme z nějakého vrcholu dále pokračovat, jednoduše vytvoříme
nový vrchol, připojíme ho jako syna tohoto vrcholu a pokračujeme do něj.
Až nalezneme vrchol odpovídající celému vkládanému slovu, nastavíme jeho bit
na jedničku. Vyhledávání řetězce
je stejně jednoduché: Z kořene se opět necháme navigovat pomocí znaků
hledaného řetězce. Pokud už dále nemůžeme pokračovat, pak hledaný
řetězec ve stromě není. Jinak jsme nalezli vrchol, který odpovídá
vyhledávanému řetězci, a podle jeho bitu poznáme, zda je řetězec ve stromě
obsažen nebo není. Poznamenejme, že existují i chytřejší implementace
této datové struktury než ta, kterou jsme si zde právě popsali.
Časová a paměťová složitost našeho programu závisí na počtu P hledaných pozic.
Pro každou z nich vytvoříme v našem stromě nejvýše K uzlů - prostorová
složitost algoritmu je tedy nejvýše O(PK). Navíc pro každou z nich
musíme vygenerovat všech nejvýše 2k-4 jejich přímých předchůdců a
pro každého z těchto předchůdců otestovat v čase O(K),
zda je v trie již obsažen. Celková časová složitost algoritmu tedy bude O(PK2).
program P_III_5;
const MAX = 200;
type uzol_sm = ^ uzol; { typ: smerník na uzol stromu }
uzol = record { typ: uzol stromu }
vetva : array[boolean] of uzol_sm; { smerníky na deti }
vlozeny : boolean; { či bol zodpovedajúci reťazec vložený }
end;
pozicia = array[1..MAX] of boolean; { typ: pozícia hry }
var koren : uzol_sm; { koreň písmenkového stromu }
K, N : integer; { K a N zo vstupu }
pocet_pozicii : integer; { počet objavených pozícií }
function novy_uzol : uzol_sm; { vytvor nový uzol stromu }
var p : uzol_sm;
begin
new(p); { alokácia pamäte }
p^.vetva[false] := nil; { uzol nemá žiadne deti }
p^.vetva[true] := nil;
p^.vlozeny := false; { zodpovedajúci reťazec nebol vložený }
novy_uzol := p; { vráť vytvorený uzol }
end; { novy_uzol }
function pridaj(var poz : pozicia) : boolean;
{ pridaj pozíciu "poz" do stromu, vráť true, ak tam ešte nebola }
var i : integer;
p : uzol_sm; { aktuálny uzol stromu }
begin
p := koren; { začneme v koreni }
for i:=1 to K do begin
if p^.vetva[poz[i]] = nil then { ak vetva neexistuje, vytvoríme }
p^.vetva[poz[i]] := novy_uzol;
p := p^.vetva[poz[i]]; { posuňme sa po príslušnej vetve }
end;
if p^.vlozeny then pridaj := false { pozícia už je v strome }
else begin { pozícia nie je v strome }
p^.vlozeny := true; { pridáme ju }
inc(pocet_pozicii); { zvýšime počet objavených pozícií }
pridaj := true;
end;
end; { pridaj }
procedure prirad(var poz : pozicia; kde : integer; b1, b2, b3 : boolean);
{ pomocná procedúra, ktorá priradí hodnoty trom políčkam pozície }
begin
poz[kde]:=b1; poz[kde+1]:=b2; poz[kde+2]:=b3;
end; { prirad }
procedure generuj(var poz : pozicia; pocet_kamenov : integer);
{ rekurzívne generuj všetky pozície z pozície "poz",
"pocet_kamenov" je počet kamenňov v "poz". }
var i : integer;
begin
if pocet_kamenov < N then begin
for i:=1 to K-2 do begin
{ skús ťah z pozície i+2 doľava }
if poz[i] and (not poz[i+1]) and (not poz[i+2]) then begin
prirad(poz, i, false, true, true); { zmeň "poz" }
if pridaj(poz) then generuj(poz, pocet_kamenov+1);
prirad(poz, i, true, false, false); { obnov "poz" }
end;
{ skús ťah z pozície i doprava }
if (not poz[i]) and (not poz[i+1]) and poz[i+2] then begin
prirad(poz, i, true, true, false); { zmeň "poz" }
if pridaj(poz) then generuj(poz, pocet_kamenov+1);
prirad(poz, i, false, false, true); { obnov "poz" }
end;
end;
end;
end; { generuj }
var i, kamen, pocet_kamenov : integer;
poz : pozicia;
begin { hlavný program }
{ načítaj a spočítaj kamene na vstupe }
readln(K, N);
pocet_kamenov := 0;
for i := 1 to K do begin
read(kamen);
poz[i] := (kamen=1);
if poz[i] then inc(pocet_kamenov);
end;
{ inicializuj globálne premenné }
koren := novy_uzol;
pocet_pozicii := 0;
{ generuj z danej pozície }
if pocet_kamenov <= N then begin
pridaj(poz);
generuj(poz, pocet_kamenov);
end;
writeln(pocet_pozicii); { vypíš výsledok }
end.