Řešení úloh ústředního kola (1. soutěžní den) 52. ročníku
P-III-1 Hračkářství
Při řešení úlohy si nejdříve uvědomíme, že ze zadaných čísel hraček můžeme
snadno odvodit, které dítě chce hračku po kterém dítěti. Situaci si představíme
jako orientovaný graf, kde vrcholy odpovídají dětem a od vrcholu i vede hrana
k vrcholu j, pokud dítě i chce hračku po dítěti j. Protože dítě je
ochotno vyměnit hračku pouze tehdy, když dostane tu svou vytouženou, mohou si
děti vyměňovat hračky pouze po cyklech - aby se dítě i
1 vzdalo své hračky,
musí dostat hračku od i
2, to od i
3 a tak dále, až nějaké dítě dostane
hračku od i
1. Chceme tedy nalézt v grafu množinu disjunktních kružnic (pro
snazší vyjadřování budeme nadále považovat za kružnici i vrchol se smyčkou),
které dohromady obsahují co nejvíce vrcholů. Hledání těchto kružnic je
usnadněno tím, že každé dvě kružnice v našem grafu jsou disjunktní - kdyby
nějaké dvě kružnice měly společný vrchol, musely by se v nějakém místě také od
sebe oddělovat. Z příslušného vrcholu by tedy musely vést dvě hrany, což ovšem
v našem grafu není možné.
A nyní jak budeme kružnice hledat: Začneme v libovolném vrcholu (třeba prvním)
a půjdeme po hranách (z každého vrcholu vede právě jedna hrana, takže postup je
jednoznačný), dokud se nevrátíme do nějakého vrcholu, ve kterém jsme už byli
(to poznáme snadno, když si budeme označovat navštívené vrcholy). Tím jsme v grafu
nalezli nějakou kružnici, tu můžeme vypsat a její vrcholy označit za vyřešené.
Vrcholy, které jsme prošli předtím, než jsme se dostali na kružnici, pro změnu
zaručeně na žádné kružnici neleží (jinak by z nějakého vrcholu musely vést
alespoň dvě hrany). Proto se těmito vrcholy už nikdy nemusíme zabývat a můžeme
je rovněž označit jako vyřešené. Nyní vezmeme další dosud nevyřešený vrchol a
opět se z něj vydáme hledat kružnici. Pokud narazíme na nějaký již vyřešený
vrchol, hledání ukončíme a projité vrcholy označíme jako vyřešené - nemohou
totiž zřejmě ležet na žádné kružnici. Když už nezbude žádný nevyřešený vrchol,
máme nalezeny všechny kružnice a výpočet ukončíme. Jediným nedořešeným
problémem zůstává, jak rychle hledat dosud nevyřešené vrcholy. To můžeme snadno
dělat tak, že při hledání dalšího nevyřešeného vrcholu začneme hledat od
naposledy nalezeného vrcholu (před ním jistě žádné nevyřešené již nejsou). Díky
tomu s hledáním vrcholů strávíme dohromady čas O(N) a protože na nalezení
kružnic potřebujeme dohromady též O(N) (každou hranou projdeme nejvýše
jednou), je celková časová složitost O(N). Paměťová složitost je také O(N).
/* Hračkářství */
#include <stdio.h>
#define MAXD 100 /* Maximální počet dětí */
int N; /* Počet dětí */
int Ma[MAXD]; /* Číslo hračky, kterou příslušné dítě má */
int Vlastni[MAXD]; /* Dítě, které vlastní příslušnou hračku */
int Chce[MAXD]; /* Dítě, jehož hračku příslušné dítě chce */
int Hotovo[MAXD]; /* Už jsme dítě řešili? */
/* Načte vstup */
void nacti(void)
{
int i;
scanf("%d", &N);
for (i = 0; i < N; i++) {
printf("Dite %d: ", i+1);
scanf("%d %d", &Ma[i], &Chce[i]);
Ma[i]--; Chce[i]--;
Vlastni[Ma[i]] = i;
}
/* Převedeme odkazy na hračky na odkazy na děti */
for (i = 0; i < N; i++)
Chce[i] = Vlastni[Chce[i]];
}
/* Projde děti a zjistí největší spokojenou skupinu */
void res(int act)
{
int start = act;
/* Projde děti a najde cyklus */
while (!Hotovo[act]) {
Hotovo[act] = 1;
act = Chce[act];
}
/* Vypíše cyklus */
while (Hotovo[act] != 2) {
Hotovo[act] = 2;
printf(" %d", act+1);
act = Chce[act];
}
/* Ještě označíme zbylé projité vrcholy */
act = start;
while (Hotovo[act] != 2) {
Hotovo[act] = 2;
act = Chce[act];
}
}
int main(void)
{
int i;
nacti();
printf("Spokojene deti:");
for (i = 0; i < N; i++)
if (!Hotovo[i]) /* Zatím jsme dítě neřešili? */
res(i);
printf("\n");
return 0;
}
P-III-2 Knihovna
Základem našeho řešení bude funkce
existuje(s:integer), která
pro zadanou šířku s rozhodne, zda existuje knihovna s P poličkami,
do které lze umístit všech N knih. Označme T součet tlouštěk knih,
tj. T=t
1+...+t
N. Potom minimální šířka knihovny
s P poličkami pro dané knihy je alespoň T/P. Na druhou stranu,
určitě existuje knihovna šířky T/P+t
max, kde t
max
je maximální tloušťka knihy: Knihy rozmístíme na poličky
tak, že každých prvních k poliček obsahuje nejmenší možný počet knih takový,
aby součet tlouštěk knih na těchto k poličkách byl alespoň kT/P.
Snadno nahlédneme, že šířka každé poličky je nejvýše T/P+t
max a
tedy existuje knihovna takové šířky. Optimální šířku skříně pak nalezneme
vyzkoušením všech hodnot mezi T/P a T/P+t
max jako možné šířky skříně.
Takových hodnot je ale konstantně mnoho kvůli omezení na tloušťku knihy ze zadání úlohy.
Ještě poznamenejme, že kdyby tloušťka knih nebyla omezena, pak by bylo
možné najít optimální šířku skříně metodou půlení intervalu pomocí
O(log T) volání funkce existuje.
Pokud by ale platilo log T > N2, bylo by výhodnější
spočítat O(N2) součtů tlouštěk i-té až j-té knihy (i<=j),
setřídit je (na to spotřebujeme čas O(N2log N)), a poté hledat
optimální šířku knihovny pouze mezi těmito součty metodou půlení intervalu.
Samotná funkce existuje bude fungovat následovně: Pro zadané s
nalezne největší i1 takové,
že t1+...+ti_1<=s; je jasné,
že i1 je
maximální možný počet knih, které lze umístit do první poličky.
Poté nalezneme největší i2 takové,
že ti_1+1+...+ti_2<=s,
tedy největší možný počet knih i2, které lze umístit do prvních dvou
poliček, atd. Pokud se nám podaří umístit všechny knihy, tj. iP=N,
pak existuje knihovna šířky s, do které lze všechny knihy uložit;
v opačném případě taková knihovna zjevně neexistuje.
Zbývá domyslet, jak rychle hledat čísla ik, 1<=k<=P, ve funkci
existuje. Za tímto účelem si nejprve vytvoříme pomocné pole,
ve kterém budou uloženy součty tlouštěk prvních j knih pro 1<=j<=N.
Při počítání hodnoty i_k metodou půlení intervalu vyhledáme v tomto
pomocném poli největší číslo i' takové, že
(t1+...+ti')-(t1+...+ti_(k-1))<=s;
zřejmě i' je hledaná hodnota ik.
Nyní odhadněme časovou a paměťovou složitost našeho algoritmu. Funkce
existuje provede P vyhledávání v poli velikosti N, tj. doba
jejího běhu je majorizována funkcí O(P log N). Celková doba běhu
našeho programu je tedy O(N+P log N);
čas O(N) spotřebujeme kromě načtení dat také na vytvoření pomocného
pole popsaného v minulém odstavci. Pokud by platilo, že P log N > N,
lze výše popsanou funkci existuje nahradit jednodušší
funkcí pracující v čase O(N), která místo P binárních vyhledávání
projde pole sekvenčně. Časová složitost našeho programu je tedy
majorizována funkcí O(N).
Paměťová složitost je O(N) - pole velikosti N je potřeba na uložení
tlouštěk jednotlivých knih a stejná je i velikost pomocného pole.
program knihovna;
const MAXN=1000;
var tloustka: array[1..MAXN] of word; { tloušťky knih }
soucet: array[0..MAXN] of word; { součty tlouštěk knih }
n: word; { počet knih }
p: word; { počet poliček }
function vyhledej(s: word): word;
var i1,i2: word;
begin
i1:=0; i2:=n;
while i1<i2 do
if soucet[(i1+i2+1) div 2]>s then
i2:=(i1+i2+1) div 2-1
else
i1:=(i1+i2+1) div 2;
vyhledej:=i1
end;
function existuje(sirka: word):boolean;
var i,j: word;
begin
i:=0;
for j:=1 to p do i:=vyhledej(soucet[i]+sirka);
existuje:=i=n;
end;
var i: word;
s1, s2: word;
tmax: word;
begin
readln(n,p);
tmax:=0;
for i:=1 to n do
begin
read(tloustka[i]);
if tmax<tloustka[i] then tmax:=tloustka[i]
end;
soucet[0]:=0;
for i:=1 to n do soucet[i]:=soucet[i-1]+tloustka[i];
s1:=soucet[n] div p;
s2:=soucet[n] div p+tmax;
while s1<s2 do
if existuje((s1+s2) div 2) then
s2:=(s1+s2) div 2
else
s1:=(s1+s2) div 2+1;
writeln('Optimální šířka skříně: ',s1,' mm');
i:=1;
while i<=n do
begin
write('Knihy na poličce:');
s2:=0;
while (i<=n) and (s2+tloustka[i]<=s1) do
begin
write(' ',i,'(',tloustka[i],' mm)');
s2:=s2+tloustka[i];
inc(i);
end;
writeln;
end
end.
P-III-3 Reverzibilní výpočty: Sčítání
Inspirujeme se tradičním algoritmem pro sčítání čísel "pod sebou"
a uvědomíme si, že není závislý na použité číselné soustavě (zvědavější
povahy obětují 5 minut na důkaz indukcí). Pokud bychom uměli spočítat přenosy mezi řády,
je samotné sečtení triviální: A'
i = A
i xor B
i xor P
i,
kde P
i je přenos z (i-1)-ního do i-tého řádu (xor funguje úplně
stejně jako sčítání dvou bitů modulo 2). Pokud jsme ochotni
obětovat paměť na všechna P
i, můžeme je spočítat postupně: P
0=0;
pro i>0 je P
i=1, když buďto A
i-1 a B
i-1 jsou současně jedničky
nebo když alespoň jedno z nich je jednička a P
i-1 je jednička.
Z toho okamžitě dostáváme program s lineární časovou i prostorovou složitostí:
procedure Add(var n:word; var A,B:array [0..n-1] of bit);
var P:array [0..n] of bit;
begin
wrap
for var i = 0 to n-1 do
P[i+1] ^= (A[i] and B[i]) or ((A[i] or B[i]) and P[i])
on
for var i = 0 to n-1 do
A[i] ^= B[i] xor P[i]
end;
My se ovšem s lineárním množstvím paměti nespokojíme a zkusíme být při výpočtu
přenosů šetrnější. Celý problém je v tom, že na spočtení P
i potřebujeme
P
i-1, a to musí být dostupné i v okamžiku, kdy budeme P
i odpočítávat
(pokusy o odpočítávání P
i pomocí P
i+1 selhávají na tom,
že když už jsme si jednoho ze sčítanců přepsali vysledkem, nelze určit,
zda jednička z výsledku vznikla z jedničky v přepsaném sčítanci nebo
z nuly a přenosu z nižšího řádu). Takže si musíme P
i-1 celou dobu
pamatovat a prostorová složitost prostě musí být vždy alespoň lineární
a naše první řešení je optimální ... a nebo přeci jen ne? Nešlo by na P
i-1
zapomenout a až budeme chtít P
i odpočítat, tak si P
i-1 spočítat znovu? To by
fungovalo, ale musíme to provést šikovně, abychom rekurzivním voláním
výpočtů předchozích P
j nespotřebovali více paměti, než jsme ušetřili.
Sestrojíme si proceduru Prenos(i,l,in,out), která pro nějaký úsek čísel
A a B (konkrétně od i-tého řádu do (i+l-1)-ního) za předpokladu,
že přenos do našeho úseku z nižších řádů Pi=in, spočítá přenos
Pi+l do vyšších řádů a přixoruje jej k proměnné out.
Pokud je úsek jednoprvkový, udělá to již dobře známým způsobem z našeho
prvního řešení (v konstantní paměti). Větší úsek si rozdělí na poloviny,
rekurzivně si spočítá přenos mid z nižší poloviny do vyšší, pak
rekurzivně spočítá přenos z vyšší poloviny "ven" a nakonec mid
třetím rekurzivním zavoláním odpočítá. To se dá jako obvykle snadno
zapsat pomocí příkazu wrap:
procedure Prenos(var i,l:word; var in,out:bit);
var l1,l2,j:word;
var mid:bit;
begin
if l=1 then { jednobitový přenos }
out ^= (A[i] and B[i]) or ((A[i] or B[i]) and in)
else wrap begin
l1 += l div 2; { l1=délka dolní poloviny }
l2 += l-l1; { l2=délka horní poloviny }
j += i+l1; { j=začátek horní poloviny }
Prenos(i,l1,in,mid) { přenos přes dolní polovinu }
end
on Prenos(j,l2,mid,out) { přenos přes horní polovinu }
end;
Jelikož při každém rekurzivním volání klesne l minimálně na polovinu,
je hloubka rekurze nejvýše [log
2l], takže procedura
Prenos
dosahuje prostorové složitosti O(log l). Se složitostí časovou je to trochu obtížnější:
Označíme-li si čas strávený touto procedurou T(l), bude platit
T(l)=1+3*T(l/2): procedura vykoná nějakou konstantní práci
(jelikož nás složitost zajímá jen asymptoticky, můžeme předpokládat,
že jednotkovou), načež třikrát zavolá sama sebe na vstup poloviční délky.
Dosadíme-li tento vztah do sebe sama, dostaneme T(l)=1+3*(1+3*T(l/4))=1+3+9*T(l/4)
a když budeme dosazovat dál, po k krocích dojdeme k T(l)=1+3+...+3
k-1+3
k*T(l/2
k).
My ale víme, že T(1)=1, takže pro k=log
2l (naše hloubka rekurze) vyjde
T(l)=1+3+...+3
log l-1+3
log l.
To je ovšem geometrická řada se
součtem (3
k+1-1)/2=O(3
k)=O(3
log l), což můžeme ještě zjednodušit:
3
log l = (2
log 3)
log l= 2
log 3 * log l = (2
log l)
log 3 = l
log 3 <= l
1.59.
Z toho plyne, že časová složitost celé procedury je T(l)=O(l
1.59).
Teď bychom mohli rekurzivní výpočet přenosů zapojit do naší původní sčítací
procedury (musíme ovšem sčítat pozadu, abychom si nepřepsali hodnoty, ze kterých
budeme přenosy ještě potřebovat) a získat tak sčítání s logaritmickou prostorovou
složitostí v čase O(n*n1.59) = O(n2.59), ale neuděláme to, protože si všimneme, že každý
z blokových přenosů bychom počítali zbytečně mnohokrát.
Místo toho zkonstruujeme podobnou rekurzivní proceduru, která bude provádět
současně sčítání a počítání přenosu. Nazveme ji Secti a bude mít
úplně stejné parametry jako procedura Prenos. Nejdříve si zavolá proceduru
Prenos pro výpočet přenosu z dolní poloviny bloku (ten opět přixoruje
k proměnné mid), pak rekurzivním zavoláním sebe sama sečte horní polovinu
čísla a nakonec rekurzivně zavolá sebe sama pro dolní polovinu čísla, čímž
ji jednak sečte a jednak odpočítá přenos mid. Triviální případ sčítání
jednobitových čísel opět vyřešíme klasicky.
procedure Secti(var i,l:word; var in,out:bit);
var l1,l2,j:word;
var mid:bit;
begin
if l=1 then begin { jednobitové sčítání }
out ^= (A[i] and B[i]) or ((A[i] or B[i]) and in);
A[i] ^= B[i] xor in
end
else wrap begin
l1 += l div 2; { opět počítáme, kde jsou poloviny }
l2 += l-l1;
j += i+l1
end
on begin
Prenos(i,l1,in,mid); { přenos přes dolní polovinu }
Secti(j,l2,mid,out); { sečteme horní polovinu }
Secti(i,l1,in,mid) { sečteme dolní a odpočteme přenos }
end
end;
Časová i prostorová složitost naší sčítací procedury bude stejná jako
u procedury
Prenos, protože až na ošetřování triviálních případů,
které je konstantní, vypadají obě procedury úplně stejně. Sčítáme
tedy v prostoru O(log n) a čase O(n
1.59). Program vypadá takto:
procedure Add(var n:word; var A,B:array [0..n-1] of bit);
{ Zde jsou vloženy procedury Prenos a Secti }
var zero:word;
var in,out:bit;
begin
Secti(zero,n,in,out); { víme, že out vyjde nulový }
end;