Zadání úloh školního kola 44. ročníku
P-I-1
Občas se stává, že některé společnosti jsou částečnými vlastníky jiných společností,
neboť získaly část jejich akcií. Jeden podnik může vlastnit
například 12% jiného podniku. Řekneme, že společnost A kontroluje
společnost B, pokud je splněna alespoň jedna z následujících
podmínek:
- A=B
- A vlastní více než 50% B
- A kontroluje k (k>=1) společností C1, ..., Ck takových, že
Ci vlastní xi % společnosti B pro 1<=i<=k a platí
x1+...+xk > 50.
Je dán seznam trojic (i,j,p), které
znamenají, že společnost i vlastní p% společnosti j.
Napište program, který v co nejkratším čase určí
všechny dvojice (h,s) takové, že společnost h kontroluje
společnost s. Výsledek ve formě seznamu dvojic (h,s) nechť je
uspořádán podle rostoucí hodnoty h.
P-I-2
Typizovanou krychlí rozumějme krychli mající tyto vlastnosti:
-
Její stěny jsou rovnoběžné se souřadnými rovinami
-
Délka jejích hran je 1/2k, k=0,1,2,...
-
Souřadnice jejích vrcholů jsou celočíselnými násobky délky jejích hran
a jsou v absolutní hodnotě menší nebo rovny 1/2
Typizované krychle ve třírozměrném prostoru jsou pro účely
uchování informace v počítači kódovány řetězci složenými z číslic 1,...,8.
Jediná typizovaná krychle velikosti 1 (dále označovaná jako "základní krychle") má kód
"" (prázdný řetězec). Má-li daná
typizovaná krychle kód K, 8 krychlí vzniklých
rozdělením K na stejně velké typizované krychle poloviční
velikosti má kód KC, kde C je číslice podle následující tabulky:
kód krychle | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
x | + | - | - | + | + | - | - | + |
y | + | + | - | - | + | + | - | - |
z | + | + | + | + | - | - | - | - |
Každou typizovanou krychli lze zřejmě získat konečným počtem dělení
základní krychle velikosti 1.
Řešte následující úlohu. Je dán kód jedné typizované krychle
a posloupnost jejích pohybů o jednu délku hrany posouvané krychle
jako konečný řetězec písmen z množiny {R
,L
,D
,U
,F
,B
} tak, že
L
značí posuv v kladném směru osy x
R
značí posuv v záporném směru osy x
U
značí posuv v kladném směru osy y
D
značí posuv v záporném směru osy y
F
značí posuv v kladném směru osy z
B
značí posuv v záporném směru osy z
Napište program, který přečte kód jedné typizované krychle
a posloupnost jejích pohybů a na výstupu uvede kódy všech
typizovaných krychlí stejné velikosti, kterými při této
posloupnosti pohybů daná krychle projde, pokud typizovaná krychle
při těchto pohybech nepřesáhne hranice základní typizované
krychle. Jestliže posouvaná krychle při svém pohybu přesáhne
hranici základní typizované krychle, vypíše program na výstup
vhodnou zprávu.
P-I-3
Máme bílý list papíru o rozměrech a cm (šířka) x b cm (výška).
Na bílý list papíru pokládejme postupně přes sebe N obdélníků různých
barev. Strany pokládaných obdélníků jsou rovnoběžné s okraji papíru.
Části obdélníků přesahující přes okraj papíru jsou odříznuty.
Po položení obdélníků jsou vidět obrazce různých barev. Dvě
oblasti stejné barvy považujeme za část téhož obrazce, pokud mají
aspoň jeden společný bod. Jinak jsou považovány za různé obrazce.
Vaší úlohou je určit polohu každého z těchto obrazců a celkovou
plochu obdélníků, která padla mimo list papíru (tj. musela být
odříznuta).
Předpokládaný souřadný systém má počátek v levém dolním rohu
a osy jsou rovnoběžné s okraji listu, přičemž výška znamená údaj
na ose y. Data pro úlohu jsou celá nezáporná čísla a mají
následující tvar:
- na prvním řádku jsou uvedeny hodnoty a, b, N
- na každém z N dalších řádků jsou uvedeny údaje o pokládaném
obdélníku v tom pořadí, jak budou umisťovány na list, a to
v pořadí: souřadnice levého dolního rohu obdélníka, jeho šířka
a výška a kód barvy obdélníka. Bílá barva má kód 1 a ostatní
barvy jsou kódovaný čísly 2 až 64.
Vaším úkolem je napsat program, který určí barvu a plochu každého
obrazce a vypíše je v pořadí daném rostoucím číslem barvy. Na
posledním řádku uvede součet velikostí všech zbytků, které
přesahovaly přes okraj papíru.
P-I-4 T-stroje
T-stroj je tvořen řídicí jednotkou, která má konečnou paměť (tj.
může se nacházet v konečně mnoha stavech) a potencionálně nekonečnou pásku
rozdělenou na pole. V každém poli může být zapsán jeden znak
abecedy nebo je pole prázdné, tj. obsahuje speciální symbol @.
Čtecí hlava T-stroje je umístěna vždy nad určitým polem pásky
a může se pohybovat vlevo nebo vpravo o jedno pole.
Výpočet T-stroje probíhá po taktech. Na začátku výpočtu je
T-stroj v počátečním stavu, na pásce je zapsána posloupnost znaků
vstupní abecedy (vstupní slovo) a je stanovena počáteční poloha
čtecí hlavy nad páskou. V každém taktu výpočtu T-stroj přečte
znak z pole, nad nímž je čtecí hlava. Na základě tohoto znaku
a stavu řídicí jednotky (konfigurace T-stroje) se zapíše nějaký
znak do stejného pole, řídicí jednotka může změnit svůj stav
a čtecí hlava se může posunout o jedno pole doleva, doprava nebo
může zůstat nad stejným polem. V průběhu činnosti T-stroje mohou
být na pásku zapisovány kromě znaků vstupní abecedy i znaky
z abecedy pracovní. Činnost T-stroje končí v okamžiku, kdy přejde
do stavu, v němž je proveden příkaz STOP nebo když není
stanoveno, jak má jeho činnost pokračovat při kombinaci
momentálního stavu a přečteného znaku. Pokud T-stroj zastaví,
řekneme, že přepsal vstupní slovo na výstupní slovo.
T-stroj může rozhodovat některé problémy, na které jsou možné
odpovědi ano/ne. pokud se T-stroj rozhodne odpovědět ano, skončí
svoji činnost v určitém pevně stanoveném stavu Sk. Pokud se
T-stroj rozhodne odpovědět ne, skončí svoji činnost ve stavu
rozdílném od Sk.
Činnost T-stroje lze popsat řídicími strukturami Pascalovského
typu, jmenovitě lze použít podmíněné příkazy a cykly typu repeat
a while. Návěstí před příkazem značí stav T-stroje. Stav S0 je
zpravidla počátečním stavem T-stroje. Jediná proměnná se jménem
znak obsahuje znak pole, nad nímž je čtecí hlava, slova right
a left značí směr pohybu čtecí hlavy po pásce. Příkaz STOP značí
ukončení výpočtu T-stroje. Jestliže v popisu T-stroje není
uvedena reakce na určitou konfiguraci (tj. čtený znak a stav
řídicí jednotky), činnost T-stroje rovněž končí.
Příklad 1
Zjistěte, zda celé kladné číslo, zapsané na pásce
v binární číselné soustavě, je liché. Čtecí hlava je nad číslicí
nejvyššího řádu.
Řešení
Sudost nebo lichost čísla v binární soustavě se pozná
podle číslice nejnižšího řádu. Pokud je 1, je číslo liché. pro
řešení naší úlohy přesuneme čtecí hlavu bez jakéhokoliv zápisu
nad poslední cifru tak, že čtecí hlavu posuneme nad první volné
pole za číslem, vrátíme se na poslední číslici a tu otestujeme.
Je-li 1, T-stroj se zastaví ve stavu S2 a odpověď je ano,
v opačném případě T-stroj zastaví ve stavu S1 a odpověď je ne.
S0: while znak<>@ do begin right end;
begin left; S1 end;
S1: if znak=1 then begin S2 end else STOP {číslo je sudé};
S2: STOP {číslo je liché}:
Příklad 2
Na pásce je nezáporné celé číslo n zapsané v binární
číselné soustavě a čtecí hlava je nad číslicí nejvyššího řádu.
T-stroj zapíše na pásku číslo n+1.
Řešení
T-stroj otestuje číslici nejnižšího řádu, připočte k ní
jedničku a provede všechny nezbytné přenosy do vyšších řádů.
S0: while znak<>@ do begin right end;
begin left; S1 end;
S1: while znak=1 do begin znak:=0; left end;
begin znak:=1; S2 end;
S2: STOP {n+1};
Poznámka: Z uvedených příkladů vyplývá, že přiřazovací příkaz
znamená zápis do pole pásky, nad níž je čtecí hlava, a příkaz Sk
znamená změnu stavu T-stroje na stav Sk. Reakci T-stroje na
konfiguraci v daném taktu zapisujeme do závorek begin a end.
Soutěžní úlohy
- Popište činnost T-stroje, který rozhodne, zda celé nezáporné
dekadické číslo je dělitelné třemi.
- Na pásce T-stroje je vstupní slovo složené z písmen a, b.
Přepište toto vstupní slovo na výstupní slovo do stejného místa
pásky tak, aby výstupní slovo obsahovalo stejný počet písmen
a i b jako vstupní slovo a všechna písmena a ve výstupním slově
předcházela všem písmenům b.