Matematická olympiáda – kategorie P

Zadání úloh ústředního kola (1. soutěžní den) 44. ročníku

P-III-1

 Typizované krychle ve třírozměrném prostoru jsou pro účely uchování informace v počítači kódovány nezápornými přirozenými čísly složenými z číslic 1..8. Souřadná soustava, v níž je umístěna základní typizovaná krychle, má počátek v jejím těžišti a souřadné osy jsou kolmé na stěny krychle. Souřadné roviny xy, yz a xz ji rozdělí na 8 menších typizovaných krychlí. Je-li A[x,y,z] bod základní typizované krychle, přiřadíme menší krychli, která ho obsahuje, podle znamének x, y, z kód dle následující tabulky:
Kód krychle 1 2 3 4 5 6 7 8
x + - - + + - - +
y + + - - + + - -
z + + + + - - - -
Každou z 8 takto vzniklých typizovaných krychlí lze rozdělit podobným způsobem; kódy vzniklých krychlí dostaneme přidáním cifry (dle tabulky) odpovídající pozici nově vzniklé krychle za pravý konec bezprostředně nadřazené typizované krychle, tzn. jejich kódy budou 11, 12, ..., 88.

Tímto způsobem lze postupně dělit typizované krychle bez omezení.

Je dána množina typizovaných krychlí K. Průměty typizované krychle do souřadných rovin xy, yz a xz (typizované čtverce) jsou kódovány pouze kódy dané souřadné roviny, tzn. tak, jako by zbývající souřadnice byla vždy kladná (například průměty typizovaných krychlí do roviny xy jsou kódovány posloupnostmi číslic 1, 2, 3, 4, analogicky u ostatních rovin).

Nechť M a Mmin jsou 2 množiny typizovaných čtverců takové, že M je průmět množiny typizovaných krychlí K do jisté souřadné roviny. Mmin je minimální k M, jestliže platí současně

Vaší úlohou je pro množinu K typizovaných krychlí zadanou jejich kódy určit minimální průměty do všech tří souřadných rovin.

P-III-2

Mějme bílý list ve tvaru obdélníka o šířce a cm a délce b cm (a<b) z nekonečně tenké a absolutně pružné látky. Zavedeme souřadný systém tak, že má počátek v levém dolním rohu papíru a osy jsou rovnoběžné s okraji listu. Tento obdélník je zdeformován tak, že protilehlé delší okraje tohoto listu jsou slepeny a vznikne válec. Ten je dále ohnut tak, že slepíme podstavy tohoto válce (překryv nutný ke slepení zanedbejte). Vznikne prostorové těleso, připomínající pneumatiku (V matematice se takové těleso nazývá toroid). Umístění souřadných os vůči původnímu listu přitom zůstane zachováno. Na toto těleso je postupně pokládáno N obdélníků z nekonečně tenké a pružné látky různých barev, jejich strany jsou rovnoběžné se souřadnými osami. Po položení všech obdélníků jsou vidět obrazce různých barev. Dvě oblasti stejné barvy považujeme za části téhož obrazce, mají-li společný alespoň jeden bod (tj. stačí dotyk rohem). Vaší úlohou je určit plochu každého z těchto obrazců.

Zadání je uvedeno v následujícím tvaru:

Výstupem programu jsou velikosti a barvy jednotlivých obrazců, setříděné v rostoucím pořadí podle čísla barvy.

P-III-3

T-stroj je tvořen řídící jednotkou, která se může nacházet v konečně mnoha stavech, a nekonečně dlouhou páskou, rozdělenou na jednotlivá pole. V každém poli může být zapsán 1 symbol nějaké konečné abecedy, nebo může být prázdné, tj. obsahovat speciální symbol @. Hlava T-stroje je umístěna vždy nad určitým polem pásky a může se pohybovat vlevo nebo vpravo právě o 1 pole.

Výpočet T-stroje probíhá v taktech. Na začátku výpočtu je T-stroj v počátečním stavu, na pásce je zapsána posloupnost znaků z dané abecedy (vstupní slovo) a je stanovena poloha hlavy nad páskou. V každém taktu výpočtu T-stroj přečte znak z pole pásky, nad nímž je umístěna hlava, a na základě tohoto znaku a stavu řídicí jednotky (konfigurace T-stroje) se zapíše nějaký znak dané abecedy do stejného pole, změní se stav řídící jednotky a hlava se může posunout o 1 pole doleva nebo doprava, případně zůstat na stejném poli. Zapsaný znak nemusí být součástí vstupní abecedy - je možné používat pomocné symboly. Činnost T-stroje končí v okamžiku, kdy vykoná instrukci STOP nebo když není definováno, jak má jeho činnost pokračovat pro příslušnou konfiguraci (znak+stav stroje). Pokud se T-stroj zastaví, říkáme, že přepsal vstupní slovo na výstupní slovo.

T-stroj může rozhodovat problémy, na které jsou možné odpovědi ano/ne. Pokud se stroj při zastavení nachází v určitém pevně stanoveném stavu, je odpověď ano, jinak ne.

Činnost T-stroje lze popsat řídícími strukturami podobnými Pascalu, jmenovitě lze použít podmíněné příkazy a cykly typu repeat a while. Návěští před příkazem značí stav T-stroje. Stav S0 je zpravidla počátečním stavem. Jediná proměnná se jménem znak obsahuje znak pole, nad nímž je hlava. Příkaz STOP ukončí výpočet T-stroje, rovněž tak, není-li uvedena reakce na určitou konfiguraci.

Příklad

Zjistěte, zda kladné celé číslo, zapsané na pásce v binární číselné soustavě je liché. Hlava je na počátku nad číslicí nejvyššího řádu, číslo pokračuje směrem doprava. Zbytek pásky je obsazen znaky @.

Řešení

Sudost nebo lichost čísla v binární soustavě se pozná podle číslice nejnižšího řádu. Je-li tato 1, odpovědí má být ano, jinak ne. Pro řešení naší úlohy přesuneme hlavu nejprve nad první pole vpravo, obsahující znak @, tj. o 1 pozici za konec čísla (během tohoto přesunu obsah pásky neměníme, tj. pokaždé na dané pole zapíšeme původní znak). Poté se vrátíme o jednu číslici zpět a otestujeme ji. Je-li to 1, T-stroj zastavíme ve stavu S2 (odpovídajícím odpovědi ano), jinak ve stavu S1 a odpověď je ne.

S0: if znak <> @ then right else begin left; S1 end; S1: if znak = 1 then S2 else STOP; S2: STOP;

Příklad

Na pásce je nezáporné celé číslo n v binární soustavě, 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. Je-li to 0, zapíše místo ní 1 a končí. Jinak ji přepíše na 0, posune hlavu o jeden znak doleva a celý postup opakuje, dokud nenarazí na nulu nebo konec slova.

S0: if znak <> @ then right else begin left; S1 end; S1: if znak = 1 then begin znak:=0; left end else begin znak:=1; S2 end; S2: STOP Z uvedených příkladů vyplývá, že přiřazovací příkaz znamená zápis do pole pásky, nad nímž je hlava, a příkaz Sk změnu stavu stroje na Sk. Reakci T-stroje na konfiguraci v daném taktu zapisujeme do bloku begin ... end

Unární číselná soustava

Celá nezáporná čísla mohou být na pásce T-stroje zapsána v unární číselné soustavě jako posloupnosti znaků "/". Délka takové posloupnosti je o 1 větší než hodnota čísla, tj. číslo 5 je zpasáno na pásce jako //////, číslo 2 jako ///. Nula je zapsána jako /.

Soutěžní úlohy

Čísla jsou na pásce zapsána v unární číselné soustavě. Hlava je v obou případech nad nejlevějším znakem vstupního slova.

  1. Vstupním slovem T-stroje je dvojice celých nezáporných čísel oddělených znakem "*". T-stroj určí a na pásku zapíše v unární soustavě jako výstupní slovo hodnotu jejich součinu.

    Příklad

    T-stroj přepíše vstupní slovo ////*/// na výstupní slovo /////// (3*2=6).

  2. Vstupním slovem T-stroje je dvojice celých kladných čísel oddělených znakem "*". T-stroj určí a na pásku zapíše v unární soustavě jako výstupní slovo hodnotu jejich největšího společného dělitele.

    Příklad

    T-stroj přepíše vstupní slovo ///////*///// na /// (NSD(6,4)=2).