Matematická olympiáda – kategorie P

Zadání úloh oblastního kola 44. ročníku

P-II-1

 Jistá banka vlastní základní kapitál v m (1<=m<=10) různých navzájem nesměnitelných měnách, konkrétně z[1] jednotek měny 1, z[2] jednotek měny 2, atd. Do banky přicházejí klienti, očíslovaní 1..n (n<=1000), aby si půjčovali peníze. Při prvním příchodu sdělí klient bankovnímu úředníkovi své celkové požadavky na výši půjčky v jednotlivých měnách. Pokud jeho požadavky nepřevýší základní kapitál, je s ním uzavřena smlouva o půjčce, kterou může klient postupně čerpat a po dokončení svých obchodů ji zase vrátí. Půjčka je bezúročná.

Bankovní úředník se snaží předejít tomu, aby banka zbankrotovala. K bankrotu banky by došlo, pokud by nebyla schopna plnit své smluvní zakázky. Požádá-li tedy klient o vyplacení další části své půjčky, ověří úředník, zda poskytnutím požadované částky klientovi nedojde v budoucnu k bankrotu banky. Pokud by taková situace mohla nastat, odkáže úředník klienta na pozdější dobu.

Můžeme předpokládat, že klient po vyčerpání celé částky ji vrátí celou a natolik rychle, že ostatní klienti mohou do té doby počkat, než obdrží další požadovanou část své půjčky.

Příklad

Nechť banka vlastní 10 jednotek jisté měny a přijala již 3 klienty s celkovými požadavky 8, 3 a 9 jednotek a tito klienti již mají půjčeno 4, 2 a 2 jednotek. V dané situaci požadavek 2. klienta na 1 jednotku je akceptován, zatímco 3. zákazník požadující 1 jednotku je odkázán na pozdější dobu.

Vaším úkolem je napsat program, který pro zadaný stav systému (tj. základní jmění banky, seznam klientů s jejich cílovými požadavky a již vypůjčenými částkami) načte číslo klienta a jeho požadavky na výši vyplacené částky v jednotlivých měnách a odpoví buď POŽADAVEK KLIENTA AKCEPTOVÁN nebo KLIENT ODKÁZÁN NA POZDĚJŠÍ DOBU.

P-II-2

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í.

Množina M typizovaných krychlí je souvislá, pokud pro každé 2 krychle A, B z M existuje posloupnost A=C0, C1, C2, .., Ck=B krychlí z M taková, že stěny krychlí Ci a Ci+1 se dotýkají pro všechna i=0,1,..,k-1; k může být i 1 (tj. A a B se dotýkají). Sousedící krychle se musejí dotýkat stěnou, nestačí dotyk hran či rohů.

Vaší úlohou je pro vstupní množinu typizovaných krychlí zadaných svými kódy určit, zda je souvislá. Krychle nemusí být stejné velikosti.

P-II-3

Bílý list papíru o šířce a cm a délce b cm (a<b) je stočen tak, že protilehlé delší okraje tohoto listu jsou slepeny tak, že vznikne válec (překryv nutný ke slepení zanedbejte). Na tento válec je postupně pokládáno N obdélníků různých barev, jejich strany jsou rovnoběžné s okraji papíru. Pokud část obdélníka (resp. celý obdélník) přesahuje okraj papíru, je oříznut. 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ů a plochu oříznutých částí obdélníků.

Souřadný systém má počátek v levém dolním rohu papíru a osy jsou rovnoběžné s okraji listu. 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, a velikost oříznuté části.

P-II-4

 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

Soutěžní úlohy

  1. Na pásce T-stroje je vstupní slovo, složené ze znaků a, b. Zjistěte, zda tato posloupnost obsahuje stejný počet znaků a i b, a tento výsledek vraťte nastavením vhodného stavu T-stroje. V případě kladné odpovědi musí po skončení výpočtu na pásce zůstat původní slovo (v případě záporné odpovědi může být stav pásky libovolný).
  2. Na pásce T-stroje je vstupní slovo, složené ze znaků a, b, c. T-stroj zdvojí tuto posloupnost tak, že za původní poslopnost ji uvede ještě jednou, ale v opačném pořadí (tedy vstup acbba přepíše na acbbaabbca).