Matematická olympiáda – kategorie P

Ř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ě i1 vzdalo své hračky, musí dostat hračku od i2, to od i3 a tak dále, až nějaké dítě dostane hračku od i1. 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=t1+...+tN. 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+tmax, kde tmax 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+tmax 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+tmax 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 = Ai xor Bi xor Pi, kde Pi 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 Pi, můžeme je spočítat postupně: P0=0; pro i>0 je Pi=1, když buďto Ai-1 a Bi-1 jsou současně jedničky nebo když alespoň jedno z nich je jednička a Pi-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í Pi potřebujeme Pi-1, a to musí být dostupné i v okamžiku, kdy budeme Pi odpočítávat (pokusy o odpočítávání Pi pomocí Pi+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 Pi-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 Pi-1 zapomenout a až budeme chtít Pi odpočítat, tak si Pi-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 Pj 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 [log2l], 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+...+3k-1+3k*T(l/2k). My ale víme, že T(1)=1, takže pro k=log2l (naše hloubka rekurze) vyjde T(l)=1+3+...+3log l-1+3log l. To je ovšem geometrická řada se součtem (3k+1-1)/2=O(3k)=O(3log l), což můžeme ještě zjednodušit: 3log l = (2log 3)log l= 2log 3 * log l = (2log l)log 3 = llog 3 <= l1.59. Z toho plyne, že časová složitost celé procedury je T(l)=O(l1.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(n1.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;