Matematická olympiáda – kategorie P

Řešení úloh domácího kola 47. ročníku

Tento pracovní materiál není určen přímo pro studenty - účastníky olympiády. Má pomoci učitelům na školách při přípravě konzultací a pracovních seminářů pro řešitele soutěže, členům oblastních výborů MO slouží jako podklad pro opravování úloh domácího kola MO-P. Studenti mohou tyto komentáře obdržet až po stanoveném termínu pro odevzdání řešení úloh domácího kola MO-P jako informaci, jak se měly úlohy správně řešit, a pro svou odbornou přípravu na účast v oblastním kole soutěže.

P-I-1 Večírek

Prvního hosta můžeme umístit dvěma způsoby - do jedné nebo do druhé místnosti. Jakmile zvolíme jeho umístění (třeba do místnosti 1), je nezbytné usadit do místnosti 2 všechny hosty, s nimiž se první host nezná. Pokud by se mezi nimi našli dva, kteří se neznají, úloha nemá žádné řešení. Jinak je umístíme do místnosti 2 a jsme pak nuceni umístit do místnosti 1 všechny takové hosty, s nimiž se někdo z místnosti 2 nezná. Podobně postupujeme tak dlouho, dokud je nějaké umístění hostů takto vynuceno. Jestliže jsme tímto postupem rozmístili všech N hostů, jsme hotovi a řešením úlohy jsou původní 2 možnosti, s nimiž jsme začínali u prvního hosta (všechna ostatní umístění byla vynucena pravidly hry). Jestliže naopak zůstali nějací zatím neumístění hosté, můžeme jednoho libovolného z nich umístit do jedné z místností a začít od něj umisťovat další jako na začátku. Pokud se nám takto K-krát stane, že někoho můžeme umístit libovolně, existuje celkem 2K způsobů, jak lze všechny hosty rozdělit do dvou místností.

Jedná se vlastně o klasickou úlohu teorie grafů. Hosté představují vrcholy grafu, hrany odpovídají vztahu "neznat se" mezi hosty. O takovémto grafu zjišťujeme, zda je bipartitní, tzn. zda lze jeho vrcholy rozdělit do dvou skupin tak, aby v rámci ani jedné skupiny nevedla žádná hrana. Pokud graf bipartitní není, úloha nemá řešení. Jestliže bipartitní je, počet přípustných rozdělení vrcholů do dvou skupin je roven 2^(počet komponent souvislosti). Komponenty souvislosti přitom není třeba zvlášť vyhledávat, neboť algoritmus na testování bipartitnosti si je určuje sám.

Algoritmus řešení této úlohy je založen na vhodném procházení grafu. Stejně jako při prostém určování komponent souvislosti grafu můžeme použít libovolný způsob procházení, do hloubky nebo do šířky. Hostům zařazeným do první místnosti přiřadíme hodnotu 1 a hostům z druhé místnosti hodnotu -1. Na začátku výpočtu není žádný host nijak zařazen (má přiřazenu hodnotu místnosti 0).

Konečnost výpočtu je dána tím, že v každém kroku je umístěn jeden host. Počet kroků výpočtu je tedy roven nejvýše počtu všech hostů N. Odtud plyne, že časová složitost algoritmu je úměrná N2, neboť každý krok výpočtu představuje provedení až kN operací pro vhodnou konstantu k (jeden průchod přes všechny "neznámé" právě zařazeného hosta).

program Vecirek; {Rozdělení hostů do dvou místností - bipartitní graf} const MaxN=100; {maximální možný počet hostů} var A:array[1..MaxN,1..MaxN] of boolean; {matice známých} Mistnost:array[1..MaxN] of -1..1; {umístění hostů} Zasob:array[1..MaxN] of 1..MaxN; {pracovní seznam hostů} Vrchol:0..MaxN; {index posledního prvku seznamu} N:1..MaxN; {skutečný počet hostů} Zarazeno:integer; {počet umístěných hostů} Konflikt:boolean; {hosty nelze rozdělit} K:1..MaxN; {počet komponent souvislosti} V:longint; {výsledný počet rozdělení} i,j:integer; begin {Inicializace proměnných a načtení vstupních dat:} write('Počet hostů: '); readln(N); for i:=1 to N do begin for j:=1 to N do A[i,j]:=false; {zatím nikdo nikoho nezná} Mistnost[i]:=0 {zatím nikdo není umístěn} end; writeln('Seznam všech dvojic známých:'); while not eof do begin read(i,j); A[i,j]:=true; A[j,i]:=true {vztah "znát se" je symetrický} end; {Umisťování hostů:} Zasob[1]:=1; {první host} Vrchol:=1; {v seznamu umístěných je zatím sám} Mistnost[1]:=1; {umístěn do místnosti 1} Zarazeno:=1; {jeden host je umístěn} K:=1; {zahajujeme umisťovat první komponentu} Konflikt:=false; while (Vrchol > 0) and not Konflikt do begin j:=Zasob[Vrchol]; {odebrat číslo hosta ze zásobníku} Vrchol:=Vrchol-1; for i:=1 to N do if (i <> j) and not A[i,j] then {neznají se j, i} if Mistnost[i]=0 then begin {umístit hosta i do opačné místnosti} Mistnost[i]:=-Mistnost[j]; Vrchol:=Vrchol+1; Zasob[Vrchol]:=i; Zarazeno:=Zarazeno+1 {další host umístěn} end else if Mistnost[i]=Mistnost[j] then Konflikt:=true; {došlo ke kolizi - nelze rozdělit} if (Vrchol=0) and (not Konflikt) and (Zarazeno < N) then begin {Zásobník je prázdný, ale ještě nebyli umístěni všichni hosté ani nedošlo ke konfliktu. Libovolného dosud neumístěného hosta můžeme umístit do kterékoliv místnosti -> prvního dosud neumístěného dáme do místnosti 1} K:=K+1; {zvýšíme počet komponent souvislosti} j:=1; while Mistnost[j] <> 0 do j:=j+1; Zasob[1]:=j; {nově umístěný host} Vrchol:=1; {v seznamu umístěných je sám} Mistnost[j]:=1; {umístěn do místnosti 1} Zarazeno:=Zarazeno+1; {další host je umístěn} end end; {Vyhodnocení procesu umisťování hostů:} if Konflikt then writeln('Počet možných rozdělení hostů do místností: 0') else begin write('Počet možných rozdělení hostů do místností: '); if K <= 30 then {spočítáme hodnotu 2^K} begin V:=1; for i:=1 to K do V:=2*V; writeln(V) end else {výsledek necháme ve tvaru "2^K"} writeln('2^',K) end end.

Příklad

Při řešení úlohy bychom mohli postupovat tak, že bychom postupně generovali všechny možné skupiny nabízených výrobků a pro každou z nich bychom ověřovali její celkovou hmotnost. Takové řešení je však pro velké počty výrobků časově velmi neefektivní (časové nároky výpočtu rostou exponenciálně v závislosti na počtu výrobků). Raději proto použijeme metodu dynamického programování, která vede k řešení mnohem rychlejšímu, k řešení s polynomiální časovou složitostí.

Budeme souběžně sledovat, jak by bylo možné co nejvíce naložit "auta" o nosnostech 1, 2, 3, ..., C. Budeme brát jeden výrobek po druhém (v libovolném pořadí) a pomocí každého dalšího výrobku se vždy pokusíme zvětšit zaplnění všech uvažovaných aut. Nejlepší naložení auta nosnosti J s využitím prvních I výrobků získáme následující úvahou: Předpokládejme, že známe nejlepší možná naložení všech uvažovaných aut pomocí výběru z prvních I-1 výrobků. Nyní dostáváme navíc k dispozici ještě I-tý výrobek. Pokud je hmotnost tohoto výrobku větší než J, do J-tého auta se nevejde a nejlepší možné zaplnění auta velikosti J prvními I výrobky je proto stejné jako zaplnění prvními I-1 výrobky. V opačném případě buď k co nejlepšímu naložení auta velikosti J nový I-tý výrobek nepoužijeme, nebo ho použijeme. Z obou možností si vybereme tu příznivější, která vede k větší hmotnosti nákladu. Nyní nám už jenom zbývá popsat tyto dvě možnosti. Jestliže se rozhodneme I-tý výrobek nenaložit, bude zaplnění J-tého auta stejné jako dosud, tj. jako při optimálním zaplnění prvními I-1 výrobky. Jestliže naopak I-tý výrobek na J-té auto naložíme, můžeme snadno spočítat zbývající volný prostor v tomto autě jako rozdíl J minus hmotnost I-tého výrobku. Tento volný prostor potřebujeme co nejlépe zaplnit prvními I-1 výrobky. To však již umíme, neboť optimální naložení všech různých menších aut pomocí výběru z prvních I-1 výrobků známe.

Celý výpočet skončí ve chvíli, kdy zpracujeme všechny výrobky a získáme tak informace o nejlepším zaplnění všech uvažovaných aut libovolnými z uvažovaných výrobků. Údaj zaznamenaný u největšího auta nosnosti C udává, jak nejlépe je možné naložit toto auto. Je-li roven hodnotě C, přesné zaplnění auta je možné, v opačném případě možné není.

Programová realizace uvedeného algoritmu je poměrně snadná. Program je v podstatě tvořen dvěma vnořenými cykly. Vnější cyklus postupně prochází zadaných N výrobků, pro každý z nich se ve vnitřním cyklu přepočítává údaj o maximálním možném naložení aut o nosnostech od 1 do C. Program nemá ani příliš velké paměťové nároky. Vystačíme s jedním pracovnímim polem o C složkách, ve kterém si budeme evidovat pro každé z aut hodnotu jeho zatím nejlepšího zaplnění.

program Naklad; {Přesné zaplnění auta výběrem z předmětů - dynamické programování} const MaxC = 10000; {maximální nosnost auta} var N: integer; {počet výrobků} C: integer; {nosnost auta} A: integer; {hmotnosti jednotlivých výrobků} Z: array[0..MaxC] of integer; {zaplnění "pomocných aut"} ZZ: integer; {možnost nového zaplnění} T: text; {vstupní a výstupní data} I, J: integer; begin assign(T,'NAKLAD.IN'); reset(T); readln(T,C); {nosnost auta} readln(T,N); {počet výrobků} for J:= 0 to C do Z[J] := 0; {všechna auta jsou prázdná} for I:=1 to N do {bereme postupně výrobky} begin read(T,A); {hmotnost I-tého výrobku} for J:=C downto A do {auta od největšího!} begin {A<=J, tedy I-tý výrobek se vejde na auto J} ZZ := A + Z[J-A]; {ZZ teď udává nejlepší možné nové zaplnění J-tého auta, pokud I-tý výrobek opravdu naložíme} if ZZ > Z[J] then Z[J]:=ZZ; {vyplatí se ho naložit} end end; close(T); assign(T,'NAKLAD.OUT'); rewrite(T); if Z[C] < C then write(T,'NE') else write(T,'ANO'); close(T) end.

P-I-3 Okna

Úlohu je možné řešit více různými způsoby. Ukážeme si alespoň dva základní algoritmy. Má-li obrazovka R řádků a S sloupců (v naší úloze konkrétně R=200, S=300) a je na ní umístěno N oken, budou časová a paměťová složitost výpočtu záviset na hodnotách parametrů R, S a N. Z tohoto hlediska se také pokusíme oba uvedené postupy porovnat.

První postup řešení lze použít pouze tehdy, pokud hodnoty R, S dovolují pracovat v programu s polem velikosti SxR reprezentujícím obrazovku. (Jako první souřadnici budeme i nadále udávat vždy číslo sloupce, jako je tomu např. v knihovnách CRT a GRAPH v Turbo Pascalu.) V našem konkrétním případě činí paměťové nároky programu 300 x 200 x 1 byte = 60000 byte. Takto velké pole můžeme bez problémů používat i v programu pracujícím na PC v reálném modu. Každý prvek pole bude představovat jeden bod na obrazovce a bude udávat, zda je tento bod "volný" pro nové okno. Na začátku výpočtu bude hodnota všech prvků pole inicializována na 1 (všude je volno). V první fázi budeme číst ze vstupu údaje o jednotlivých oknech umístěných na obrazovce a plochu všech těchto oken vyznačíme v našem poli nulami. To vyžaduje vykonat maximálně O(NRS) operací, neboť každé z N oken může mít velikost až SxR. Nadále již s jednotlivými okny nebudeme vůbec pracovat, pro nové okno velikosti AxB budeme hledat v poli volné obdélníkové místo této velikosti tvořené samými 1.

Nyní bychom mohli uvažovat postupně všechny obdélníkové výřezy velikosti AxB a každý z nich zkoumat, zda je tvořen jedničkami. Tímto způsobem bychom sice dostali správné řešení úlohy, byl by to však velmi neefektivní postup. Obdélník velikosti AxB je možné umístit řádově až R.S způsoby a samostatné prozkoumání každé jeho polohy vyžaduje provést A.B testů, což může být řádově rovněž R.S. Celková časová složitost algoritmu by nám pak vyšla O(R2S2). Lepší je zařadit jako druhou fázi algoritmu pomocný předvýpočet, ve kterém určíme a zaznamenáme si délky souvislých sloupců jedniček v poli. Nulové prvky zůstanou nulové i nadále, každý jedničkový prvek však zvýšíme o počet jedniček, které leží v souvislé posloupnosti ve sloupci bezprostředně pod ním. Tato druhá fáze má časovou složitost O(RS). Provádí se totiž samostatně v každém z S sloupců a vystačíme vždy s jedním průchodem sloupcem zdola nahoru, kdy každou jedničku zvýšíme o číslo uložené v poli pod ní.

Následovat bude třetí fáze výpočtu, v níž již vyhledáme polohu nového okna v našem upraveném poli. Budeme ho procházet postupně po řádcích a hledat prvek s hodnotou alespoň B. Jen v takovém místě může totiž ležet levý horní roh jedničkového obdélníku velikosti AxB. Když takový prvek najdeme, pokračujeme v procházení téhož řádku směrem doprava a přitom kontrolujeme, zda alespoň A-1 dalších sousedních prvků má hodnotu nejméně B. Jestliže ano, našli jsem přípustnou polohu nového okna a výpočet ukončíme. Pokud ne, právě zkoumané místo v poli nepostačuje pro nové okno a pokračujeme v hledání dalších prvků s hodnotou alespoň B. Nejpozději po projití všemi prvky pole známe buď možnou polohu nového okna, nebo víme, že ho na obrazovku nelze umístit. Tato fáze výpočtu má časovou složitost O(RS) - jedná se o jeden průchod polem velikosti SxR.

Celé řešení je tvořeno inicializací pole a třemi po sobě jdoucími fázemi výpočtu. Celková časová složitost uvedeného algoritmu je tedy rovna maximu ze složitostí jednotlivých kroků, tj. O(NRS). Paměťová složitost je dána velikostí pole a je O(RS).

Druhý postup řešení nepotřebuje pole velikosti SxR, místo něj si uložíme přímo seznam všech oken a setřídíme ho vzestupně podle souřadnice levého okraje okna. Při použití dobrého třídicího algoritmu to můžeme provést v čase O(N log N). Uvažujme nyní nejprve vodorovný pás výšky B bodů podél horního okraje obrazovky. Budeme zkoumat, zda do něj lze umístit nové okno o rozměrech AxB. Projdeme uspořádaný seznam všech oken a vybereme z něj ta, která do uvažovaného pásu zasahují. Díky setřídění přitom můžeme zároveň snadno počítat, jak široké "mezery" mezi okny v pásu zůstanou volné a zda je některá z nich velká alespoň A bodů. K tomu stačí průběžně si evidovat v jedné pomocné proměnné, jak daleko doprava je v pásu již "obsazeno". Takovéto ošetření jednoho pásu provedeme v čase O(N). Pokud jsme při něm nenašli dostatečný prostor pro nové okno, musíme zkoumat další pásy. Mohli bychom se jednoduše posunout s vodorovným pásem výšky B o jeden bod níže a postupovat dál stejně. Takto bychom postupně prošli v nejhorším případě všech R-B+1 poloh uvažovaného pásu a vykonali přitom tedy celkem O(RN) operací. Lepší ale bude posunout pás rovnou o tolik bodů níže, až ho poprvé opustí některé z oken, která do něj právě zasahují. Jen tak se může v pásu vytvořit větší prostor pro nové okno. K tomu stačí evidovat si průběžně v jedné proměnné minimum ze souřadnic dolních okrajů těch oken, které do pásu momentálně zasahují. Každé z N oken opustí pás nejvýše jednou, takže bude rozhodně stačit zkoumat nejvýše N různých poloh pásu. Počet vykonaných operací se tím změní na O(N2).

Celková asymptotická časová složitost tohoto druhého algoritmu je dána složitostí vytvoření setříděného seznamu hran a složitostí vlastního výpočtu a vychází tedy O(N log N + N2)= O(N2). Paměťová složitost je určena nutností uložit si seznam oken a je rovna O(N). Jedná se tedy pravděpodobně o lepší řešení než bylo předchozí (a to i s využitím výše uvedeného zrychlujícího předvýpočtu), neboť reálně lze očekávat N2 < NRS (srovnání časových nároků) a N < RS (srovnání paměťových nároků obou algoritmů). Zvláště při větším počtu bodů na obrazovce (tzn. při vyšším rozlišení) časové i paměťové nároky prvního uvedeného řešení výrazně rostou, zatímco u druhého postupu se nemění a závisí jen na počtu oken. Teoreticky vzato však nejsou oba uvedené postupy řešení přímo srovnatelné z hlediska svých časových a paměťových nároků, neboť pro některé hodnoty parametrů může být první uvedené řešení lepší (při extrémně velkém počtu oken na obrazovce s malým rozlišením).

P-I-4 Kombinační sítě

  1. Úlohu lze řešit způsobem velice podobným tomu, jímž byla řešena úloha uvedená v zadání jako příklad, tj. metodou "rozděl a panuj". Popíšeme postup pro získání maxima (minimum se hledá analogicky).

    Předpokládejme, že počet vstupů je mocnina dvou. Pokud není, doplníme si další fiktivními vstupy o stálé hodnotě 0 (takové vstupy nám výsledek neovlivní) na nejbližší vyšší mocninu dvou. Při výpočtu minima postupujeme stejně, jen místo fiktivních vstupů s hodnotou 0 použijeme vstupy s hodnotou 9.

    Nejprve problém vyřešíme pro 2 vstupy, a to zavedením hradla MAX(a,b), jehož přechodovou funkcí bude maximum z hodnot vstupů a, b. Setrojení tabulky hradla MAX je snadné. Máme-li již problém vyřešen pro k vstupů a hledáme řešení pro 2k vstupů, rozdělíme vstupy libovolným způsobem do dvou skupin po k vstupech, nalezneme pro každou z nich maximum a poté (za pomoci hradla MAX) určíme maximum z těchto dílčích maxim. Takto nalezený výsledek je jistě maximem z daných 2k hodnot. Zapojení sítě tedy bude shodné se sítí uvedenou v ukázkovém příkladu, pouze místo hradel XOR použijeme hradla MAX:

    12345678
    MAXMAXMAXMAX
    MAXMAX
    MAX
    Výstup

    Tímto způsobem zkonstruovaná síť má přibližně log2(N) hladin, časová složitost výpočtu je proto O(log N), kde N je počet vstupů obvodu.

  2. Nejprve si zavedeme tři typy hradel OR, AND a ANDN definované následujícími tabulkami:


    ORY
    01
    X001
    111

    ANDY
    01
    X000
    101

    ANDNY
    01
    X000
    110

    Poznámka: Hradla AND a OR počítají známé základní logické funkce, hradlo ANDN má význam (x AND NOT y).

    Z těchto hradel pak sestrojíme "selektor" - jednoduchou síť se třemi vstupy S, A0 a A1 a jedním výstupem Q, která na Q přivede AS (tedy A0, pokud je S=0, nebo A1 při S=1). Budeme značit Q=SEL(A0,A1,S).
    B0 = ANDN(A0, S)
    B1 = AND(A1, S)
    Q = OR(B0, B1)
    Nyní již můžeme přikročit ke konstrukci sítě pro danou úlohu, zatím ovšem v trochu pozměněném tvaru: vstupů budeme mít n=2p (označeny X0, X1, ..., Xn-1), výstupů p+1, kde první výstup (S) bude informovat o tom, zda jednička vůbec někde byla (hodnota 1) či nikoliv (hodnota 0). Je-li S=1, potom ostatní výstupy Q0, Q1,..., Qp-1 obsahují nejmenší z čísel jedničkových vstupů, je-li S=0, ostatní výstupy mohou mít libovolné hodnoty. Výsledné číslo bude na výstupech umístěno tak, že Q0 obsahuje jeho nejnižší řád a Qp-1 řád nejvyšší.

    Pro 2 vstupy (p=1) lze tuto síť sestavit snadno:
    S = OR(X0, X1)
    Q0 = ANDN(X1, X0)
    Máme-li již řešení pro n=2p vstupů, pro 2n vstupů lze řešení rovněž sestrojit snadno: rozdělíme vstupy do dvou skupin: X0 až Xn-1 a Xn až X2n-1, přičemž pro každou z těchto skupin úlohu vyřešíme. Výstupy částečných řešení označíme M a A0 až Ap-1 pro první skupinu a N a B0 až Bp-1 pro druhou skupinu.

    Pokud je M=1, je první jednička zaručeně v první skupině, tudíž Qp bude 0 a ostatní Qi budou rovna Ai. S musí být 1.

    Pokud je M=0 a N=1, je první jednička v druhé skupině, takže Qp bude 1 a ostatní Qi budou rovna Bi. S musí být 1.

    Pokud je M=0 a N=0, žádný ze vstupů jedničku neobsahuje, proto hodnoty Qi mohou být libovolné a S bude rovno 0.

    Tyto požadavky lze snadno realizovat pomocí již definovaných hradel a bloku SEL:
    S = OR(M, N)
    Qp = ANDN(N, M)
    Qi = SEL(Ai, Bi, Qp) pro 0<= i < p
    Takto sestrojíme kombinační síť řešící upravenou úlohu pro libovolný počet vstupů rovný mocnině dvou. Na tento problém nyní zadání naší úlohy snadno převedeme: zadané vstupy doplníme (na konec) jedním vstupem o fixní hodnotě 1 na mocninu dvou - tím bude výstup S upravené úlohy vždy 1 a ostatní výstupy budou udávat buďto pozici první jedničky na zadaných vstupech nebo pozici nově přidané jedničky, která ovšem odpovídá samým jedničkám na výstupech, čímž jsme požadavky zadání přesně splnili.

    Pro počet vstupů n=2k-1 má vytvořená kombinační síť hloubku 3k-2, tudíž její výpočet má časovou složitost O(log n).