Matematická olympiáda – kategorie P

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:
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: 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 krychle12345678
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

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:

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

  1. Popište činnost T-stroje, který rozhodne, zda celé nezáporné dekadické číslo je dělitelné třemi.
  2. 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.