Matematická olympiáda – kategorie P

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

P-I-1

Připomeňme si na začátek, že fakta o firmách je vhodné representovat ve formě orientovaného grafu s ohodnocením jeho hran. Uzly tohoto grafu budou představovat firmy a orientovaná hrana jdoucí od uzlu i do uzlu j s ohodnocením p představuje fakt, že firma i vlastní p procent firmy j. Tento graf je možno representovat čtvercovou maticí M, v níž hodnota M[i,j]=p znamená, že firma i vlasní p procent firmy j.

Testování prvních dvou podmínek je triviální. Pro začátek se snažme implementovat funkci kontroluje, která dokáže rekursivně určit, zda nějaká firma i kontroluje firmu j. Pokud součet ohodnocení hran, které vcházejí do uzlu j převyšuje hodnotu 50, je splněna nutná podmínka pro to, aby firma i kontrolovala firmu j. Zdaleka to ovšem není podmínka dostatečná. Dostatečnou podmínkou pro vlasnění je, aby součet ohodnocení všech hran, vyházejících z některého uzlu, který už je vlastněn firmou i a vcházejících do uzlu j, převyšoval hodnotu 50.

Vlastní jádro algoritmu pro rekursivní stanovení toho, zda firma i kontroluje firmu j by mohlo vypadat takto:

function kontroluje(i,j:int):bool; var k,suma:int; begin if i=j then kontroluje:=true else if M[i,j] > 50 then kontroluje:=true else begin suma=0; for k:=1 to N do suma:=suma+M[k,j]; if suma <= 50 then kontroluje:=false else begin suma:=0; for k:=1 to N do if kontroluje(i,k) then suma:=suma+M[k,j]; if suma > 50 then kontroluje:=true else kontroluje:=false end end end Tato procedura by pak mohla být jednoduše použita ve dvojitém cyklu pro úplné zjištění, které firmy jsou kterými kontrolovány. Všechny takto zjištěné dvojice by se ukládaly do vhodné tabulky, případně by mohly být přímo tisknuty jako výsledek.

for i:=1 to N do for j:=1 to N do if kontroluje(i,j) then store(i,j); Na první pohled je ovšem zřejmé, že daný program nevyhovuje zadání úlohy, které požaduje, aby výsledek byl získán v co nejkratším čase. To, že jsme implementovali algoritmus rekursivně nám sigalizuje, že z hlediska úspory času je účelné použít v programu zásobníku, jehož vhodné použití nám dobu výpočtu zkrátí.

Pro implementaci programu použijeme zásobníku, ve kterém budeme používat nejen pouze vrchol, ale vždy celý úsek, do kterého si uschováme informaci o všech hranách, vcházejících do analyzovaného uzlu. Úsek zásobníku tedy bude obsahovat tolik položek, kolik je bezprostředních předchůdců analyzovaného uzlu. Pro každý uzel i (representující firmu pro níž chceme zjistit, zda není kontrolována jinou firmou j podle posledního pravidla) si do položky zásobníku zapíšeme do prvku kdo by mohl být vlastníkem koho, pokud vlastní kolik procent příslušné firmy. Pro vlastní práci se zásobníkem bude nutno udržovat dva ukazatele. Ukazatal np ukazuje na vrchol zásobníka a ukazatel sp ukazuje na první položku za analyzovaným úsekem zasobníku. V zásobníku je na každé položce dále prvek kam, který ukazuje, kam je nutno přičíst procenta vlastnění, pokud to poslední pravidlo rozhodne. Pro implementaci zásobníku použijeme celkem 4 pole s názvy kdo, koho, kolik a kam.

Pokud program rozhodne, že firma i kontroluje firmu j, poznamenáme si tuto skutečnost do prvku M[i,j] tak, že hodnotu tohoto prvku zvýšíme o 200.

Vytisknout výsledky v požadované podobě je nyní již triviální.

program VLASTNENI(input,output); const MAX=100; N=100; var kdo,koho,kolik,kam:array[0..MAX] of int; M:array [1..N,1..N] of int; i,j,k,N,p,sp,np,in,jn,is,js:int; function hodnotaM(i,j:int):int; begin if M[i,j] > 100 then hodnotaM:=M[i,j]-200 else hodnotaM:=M[i,j] end; function sumaM(j:int):int; begin var l,pom:int; pom:=0; for l:=1 to N do pom:=pom+hodnotaM(l,j); sumaM:=pom end; begin for i:=1 to N do for j:=1 to N do M[i,j]:=0; {předpokládáme, že prvků (i,j,p)} {může být více v jednom vstupu} read(i,j,p); while not eof do begin M[i,j]:=M[i,j]+p;read(i,j,p) end; for i:=1 to N do for j:=1 to N do if M[i,j] > 50 or i=j then M[i,j]:=M[i,j]+200; {otestujeme platnost prvních dvou podmínek a zapíšeme do M} {poté začneme testovat poslední podmínku} for i:=1 to N do for j:=1 to N do {pokud má smysl testovat další dvojici} if i <> j and M[i,j] < 200 and sumaM(j) > 50 then begin {ulož ji na dno zásobníku a} sp:=0; np:=1;kdo[np]:=i;koho[np]:=j;kolik[np]:=0;kam[np]:=sp; while np <> 0 do {do vyprázdnění zásobníku} begin in:=kdo[np];jn:=koho[np]; if M[in,jn] >= 200 then {pokud i kontr. předch j} begin js:=koho[sp];is:=kdo[sp]; kolik[sp]:=kolik[sp]+hodnotaM(jn,js); if kolik[sp] > 50 then {a poslední podm. je splněna} begin M[is,js]:=M[is,js]+200; np:=sp {další hrany netestujeme} end else np:=np-1; {jinak vezmi další hranu} if np=sp then {pokud je úsek zás.zprac.} begin sp:=kam[sp]; if sp=0 then np:=0 end {test předch. úseku} end else {pokud i nekontr.předch.j} if sumaM(jn) > 50 then {a nutná podmínka platí} begin sp:=np;js:=koho[sp]; for k:=1 to N do if M[k,js] > 0 then begin np:=np+1; kdo[np]:=kdo[sp]; koho[np]:=k;kam[np]:=sp; kolik[np]:=0 end{vytvoříme další úsek zásobníku} end else np:=np-1 {jinak dvojici ignorujeme} end end; {všechny hrany otestovány} for i:=1 to N do for j:=1 to N do if M[i,j] >= 200 then writeln(i,j) end.

P-I-2

Pro návrh algoritmu si nejdříve všimněme, jak se mění kódy typizované krychle po jednom pohybu v některém z možných 6 směrů. Doporučujeme Vám, abyste si načrtli vhodný obrázek. Pokud se pohyb uskuteční v rámci bezprostředně nadřazené krychle, mění se pouze její kód v nejnižším řádu. Jeho změny je možno si poznamenat do tabulky. Půjde o tabulku T o 6-ti řádcích a osmi sloupcích, v níž jsou poznamenány kódy po provedení 1 pohybu. Například kód 1 ve 4. sloupci a 3. řádku značí, že po provedení tahu "U" z oktantu 4 se dostaneme do oktantu 1.

Může se ovšem stát, že krychle po jenom pohybu překročí hranice některých typizovaných krychlí "větších" než je bezprostředně nadřazená krychle. Potom je nutno po provedení 1 pohybu změnit kódy odpovídající všem takovým nadřazeným krychlím. To je vhodné mít v tabulce rovněž poznamenáno například tak, že příslušný kód zvětšíme o 10. Tak kód 16 v 7. sloupci a 4. řádku v tabulce značí, že pohybem "D" se dostaneme přes hranice bezprostředně nadřazené typizované krychle, poslední cifra kódu přesunuté krychle bude 6 a je nutno zajistit přenos do vyšších řádů kódu, realizovaný rovněž pomocí této tabulky. Popsaným způsobem postupujeme, pokud v příslušném kóku je uveden příznak přenosu.

12345678
1 L 12 1 41316 5 817
2 R2 1 4 3 61518 7
3 U 1413 2 11817 6 5
4 D4 31211 8 71615
5 F 15161718 1 2 3 4
6 B5 6 7 811121314
Poznámka: Je to podobná situace, jako kdybychom si vytvořili tabulku pro sčítání dekadických čísel, v níž bychom si pamatovali přenosy do vyšších řádů.

Fakt, že přesouvaná krychle přešla přes kranice základní typizované krychle, poznáme podle toho, že je registrován přenos, i když už kódy všech nadřazených krychlí už byly vyčerpány.

Pro vlastní implementaci si budeme kód krychle pamatovat v souboru krychle, protože neexistují žádná omezení na jemnost dělení základní typizované krychle, což by nám umožňovalo stanovit meze pro použití pole. Fakt, že přesouvaná krychle překročí hranice základní typizované krychle je lehce identifikovatelný tím, že kód eof pro soubor krychle nabyl hodnoty true.

Vlastní program pak může vypadat například takto.

program KRYCHLE(input,output); const CR=13; var krychle,krychlepo:file of int; T:array[1..6,1..8] of int; znak:char; i,j:int; pokracovat,prenos:bool; begin T[1,1]:=12;T[1,2]:=1;T[1,3]:=4;T[1,4]:=13; T[1,5]:=16;T[1,6]:=5;T[1,7]:=8;T[1,8]:=17; T[2,1]:=2;T[2,2]:=11;T[2,3]:=14;T[2,4]:=3; T[2,5]:=6;T[2,6]:=15;T[2,7]:=18;T[2,8]:=7; T[3,1]:=14;T[3,2]:=13;T[3,3]:=2;T[3,4]:=1; T[3,5]:=18;T[3,6]:=17;T[3,7]:=6;T[3,8]:=5; T[4,1]:=4;T[4,2]:=3;T[4,3]:=12;T[4,4]:=11; T[4,5]:=8;T[4,6]:=7;T[4,7]:=16;T[4,8]:=15; T[5,1]:=15;T[5,2]:=16;T[5,3]:=17;T[5,4]:=18; T[5,5]:=1;T[5,6]:=2;T[5,7]:=3;T[5,8]:=4; T[6,1]:=5;T[6,2]:=6;T[6,3]:=7;T[6,4]:=8; T[6,5]:=11;T[6,6]:=12;T[6,7]:=13;T[6,8]:=14; {inicializace tabulky} rewrite(krychle); read (znak); {nacteni kodu presouvane krychle} while znak<>CR do begin case znak of '1':krychle^:=1; '2':krychle^:=2; '3':krychle^:=3; '4':krychle^:=4; '5':krychle^:=5; '6':krychle^:=6; '7':krychle^:=7; '8':krychle^:=8; end; put(krychle);read(znak); end; {kod krychle nacten} read(znak);pokracovat:=true; {pro vsechny pohyby} while znak<>CR and pokracovat do begin reset(krychle);rewrite(krychlepo); case znak of 'L':i:=1; 'R':i:=2; 'U':i:=3; 'D':i:=4; 'F':i:=5; 'B':i:=6; end; {urceni radkoveho indexu i pro T} get(krychle);prenos:=true; while not eof(krychle) and prenos do begin j:=krychle^;krychlepo^:=T[i,j]; if krychlepo^ > 10 then krychlepo:=krychlepo-10 else prenos:= false; put(krychlepo);get(krychle) end; {jeden pobyb byl registrovan} if not eof(krychle) then {vypiseme o nem informaci} begin reset(krychle);reset(krychlepo); while not eof(krychlepo) do begin get(krychlepo);write(krychlepo^:1); krychle^:=krychlepo^;put(krychle); end end else begin writeln('Mimo základni krychli'); pokracovat:=false end; writeln('');read(znak) end end.

P-I-3

Předpokládáme, že vstupní parametry splňují zadání úlohy. Pokud hodnoty rozměrů papíru a,b jsou taková čísla, že je možné je omezit konstantami A,B (a < A,b < B) tak, že matici POLE rozměrů axb celých čísel lze vložit do paměti, potom si lze barvy pokládaných obdélníků pamatovat v jednotlivých elementech tohoto pole. Samozřejmě, že je nutno předtím ořezat přesahující části obdélníků. Například nejdříve obdélníků přesahujících list papíru vpravo a pak vzhůru a započítat do ořezaných částí i ty obdélníky, které padnou celé mimo plochu papíru.

Po ořezání a určení celkové odříznuté plochy určíme velikosti ploch těch obrazců, které vidíme po položení posledního obdélníka. Můžeme to udělat například tak, že systematicky postupujeme po dvojdimensionálním poli a když narazíme na políčko s kladným číslem barvy, obrátíme jeho znaménko, abychom poznamenali, že jsme políčkem již prošli a jednotkovou plošku jsme připočetli k celkové ploše patřičného obrazce. Teď je ovšem podstatné určit plochu celého nalezeného viditelného obrazce. Můžeme to udělat například tak, že otestujeme číslo barvy všech jeho osmi sousedů. Pokud některý z nich má kód barvy shodný s kódem barvy počátečnho čtverečku, určitě patří do tohoto obrazce, takže připočítáme jeho plošku k celkové ploše právě analyzovaného obrazce a obrátíme znaménko jeho barvy. Popsaným způsobem postupujeme dokud nevyhledáme všechny čtverečky, tvořící analyzovaný obrazec.

Musíme si ovšem pamatovat v nějaké vhodné datové struktuře indexy všech čtverečků, jejichž plochy jsme již připočetli (a čísla barev jsme nastavili na záporné hodnoty), ale jejichž sousední čtverce dosud nemusely být testovány. Vhodnou datovou strukturou může být zásobník a jeho vyprázdnění testem, že jsme již prošli celým obrazcem.

S tímto zásobníkem budeme pracovat tak, že indexy prvního registrovaného čtverečku uložíme na vrchol zásobníku. Postupně z vrcholu neprázdného zásobníku vybíráme indexy už registrovaného políčka a prověřujeme jeho sousedy. Indexy každého souseda(který nesmí vybočit z listu papíru), který má shodné číslo barvy uložíme opět na vrchol zásobníku a připočteme jedničku k celkové ploše celého obrazce. Takto postupujeme, dokud nevyprázdníme zásobník.

Tabulku s údaji o velikosti viditelných obraců a jejích barev je vhodné implementovat ve formě lineárně zřetězeného seznamu, setříděného vzestupně podle čísel barev viditelných obrazců. Pro zjednodušení algoritmu ukládání prvků do této tabulky je vhodné použít zarážky na jejím konci, která obsahuje číslo barvy, které je větší, než maximální možná barva.

program OBRAZCE(input,output); const A=30; B=50; MAX=200; NIL=0; MAXINT=100; type uzel=record color,area:int, dalsi:^uzel end; var i,j,l,i0,j0,plocha,barva,pointer,a,b,N,x,y,delka,sirka:int; ii,jj:array[1..MAX] of int;pole:array[0..A,0..B] of int; obrazec,obrazce,zde:^uzel; procedure push(i,j:int); begin plocha=plocha+1;pointer:=pointer+1; pole[i,j]:=-pole[i,j]; ii[pointer]:=i;jj[pointer]:=j end; procedure pop(i,j:int); begin i:=ii[pointer];j:=jj[pointer];pointer:=pointer-1 end; begin read(a,b,N); for i:=0 to a-1 do for j:=0 to b-1 do pole[i,j]:=1; {bily papir} presah:=0; for l:=1 to N do begin read(x,y,delka,sirka,barva); if (x >= a) or (y >= b) then presah:=presah+delka*sirka else begin if (x+delka > a) then begin presah:=presah+(x+delka-a)*sirka; delka:=a-x end; {odriznuti vpravo} if (y+sirka > b) then begin presah:=presah+(y+sirka-b)*delka; sirka:=b-y end; {odriznuti nahoru} for i:=x to x+sirka do for j:=y to y+delka do pole[i,j]:=barva end {obdelnik polozen} end; {vsechny polozeny} new(obrazec);obrazce:=obrazec; with obrazec^ do begin color:=MAXINT; area:=MAXINT; dalsi:=NIL end; {inicializace tabulky} for i0:=0 to a-1 do for j0:=0 to b-1 do begin if pole[i0,j0] > 0 then begin plocha:=0;barva:=pole[i0,j0]; pointer:=0; push(i0,j0); while pointer > 0 do begin pop(i,j); if i > 0 and pole[i-1,j] =barva then push(i-1,j); if i > 0 and j < b-1 and pole[i-1,j+1]=barva then push(i-1,j+1); if j < b-1 and pole[i,j+1]=barva then push(i,j+1); if i < a-1 and j < b-1 and pole[i+1,j+1]=barva then push(i+1,j+1); if i < a-1 and pole[i+1,j]=barva then push(i+1,j); if i < a-1 and j > 0 and pole[i+1,j-1]=barva then push(i+1,j-1); if j > 0 and pole[i,j-1]=barva then push(i,j-1); if i > 0 and j > 0 and pole[i-1,j-1]=barva then push(i-1,j-1) end {testovali jsme vsemi smery} end; {cely obrazec projity} new(obrazec); with obrazec^ do begin color:=barva;area:=plocha end; if obrazce^.color > barva then begin obrazec^.dalsi:=obrazce;obrazce:=obrazec; end else begin zde:=obrazce; while (zde^.dalsi)^.color<barva do zde:=zde^.dalsi; obrazec^.dalsi:=zde^.dalsi; zde^.dalsi:=obrazec end; end; {vsechny obrazce urceny} zde:=obrazce; while zde^.barva <> MAXINT do begin with zde^ do writeln(color,area); zde:=zde^.dalsi end end

P-I-4

Úloha A

Celé dekadické číslo je dělitelné třemi, pokud součet jeho cifer je dělitelný třemi. Bez újmy na obecnosti předpokládejme, že čtecí hlava je nastavena nad číslicí nejvyššího řádu zkoumaného čísla.

Dělitelnost třemi lze zjistit jedním průchodem čtecí hlavy přes všechny cifry zkoumaného čísla. Pomocí stavů S0, S1, S2 si budeme pamatovat zbytky po dělení třemi součtu již prošlých cifer. Po projití celého čísla oznámí T-stroj dělitelnost třemi přechodem do stavu S3 a zastavením. Pokud číslo není dělitelné třemi, oznámí to T-stroj přechodem do S4 a následným zastavením.

S0: if znak=@ then S3 else if znak in {0,3,6,9} do right else if znak in {1,4,7} then begin right; S1 end else begin right; S2 end; S1: if znak=@ then S4 else if znak in {0,3,6,9} do right else if znak in {1,4,7} then begin right; S2 end else begin right; S1 end; S2: if znak=@ then S4 else if znak in {0,3,6,9} do right else if znak in {1,4,7} then begin right; S0 end else begin right; S1 end S3: STOP; (* číslo je dělitelné třemi *) S4: STOP; (* číslo není dělitelné třemi*)

Úloha B

Myšlenka algoritmu T-stroje je následující:

Dokud existuje ve slově znak b předcházející znaku a, prohazujeme nejlevější výskyt b s nejpravějším výskytem a.

Budeme používat 2 speciální znaky - B, označující místo, kde byl v minulém kroku nejpravější výskyt a, a A, označující místo nejlevějšího výskytu b.

Ve stavu S0 se budeme nacházet na místě, od nějž nalevo jsou již jen samé znaky a (na začátku na levém okraji slova). Od něj budeme postupovat doprava, dokud nenarazíme na

Ve stavu S1 jsme nalezli nejlevější výskyt b, budeme nyní hledat nejpravější výskyt a. Za tímto účelem nyní přejdeme na místo, za nímž se už žádný znak a nevyskytuje, tj. ke znaku B, resp. konci slova, a přejdeme do stavu S2. Jedná-li se o znak B, přepíšeme ho navíc na b.

Ve stavu S2 budeme hledat nejbližší výskyt a nalevo od něj. Jestliže dříve narazíme na A, znamená to, že slovo je již v požadovaném tvaru, přepíšeme ho tedy zpět na b a skončíme. Jestliže dojdeme k a, změníme ho na B a přejdeme do stavu S3.

Ve stavu S3 se vrátíme ke znaku A, přepíšeme ho na a a přecházíme do stavu S0.

S0: if znak=b then begin znak=A; S1; right end; if znak=B then begin znak=b; STOP end; if znak=@ then STOP; right; S1: if znak=@ then begin S2; left end; if znak=B then begin znak=b; S2; left end; right; S2: if znak=a then begin znak=B; S3; left end; if znak=A then begin znak=b; STOP end; left; S3: if znak=A then begin znak=a; S0; right end; left;