Řešení úloh školní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.
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
1 | L | 12 | 1 | 4 | 13 | 16 | 5 | 8 | 17 |
2 | R | 2 | 1 | 4 | 3 | 6 | 15 | 18 | 7 |
3 | U | 14 | 13 | 2 | 1 | 18 | 17 | 6 | 5 |
4 | D | 4 | 3 | 12 | 11 | 8 | 7 | 16 | 15 |
5 | F | 15 | 16 | 17 | 18 | 1 | 2 | 3 | 4 |
6 | B | 5 | 6 | 7 | 8 | 11 | 12 | 13 | 14 |
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
- Znak b - toto je nejlevější výskyt znaku
b, přepíšeme ho tedy na A a přejdeme do
stavu S1.
- Znak B - napravo od tohoto místa se již
nevyskytuje žádné a, nalevo od něj není žádné
b, tedy ho přepíšeme na b a skončíme.
- Konec slova - to znamená, že slovo neobsahuje žádný znak
b, tedy splňuje danou podmínku a skončíme.
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;