Matematická olympiáda – kategorie P

Zadání úloh domácího kola 45. ročníku

Všeobecné pokyny

Řešení každého příkladu musí obsahovat (není-li uvedeno v textu zadání úlohy něco jiného):

P-I-1

Trojúhelníková síť se skládá z rovnostranných trojúhelníků jednotkové velikosti. Soustavu souřadnic si nyní trochu pozměníme: x-ová osa bude orientována stejně, jako jsme zvyklí z kartézské soustavy souřadnic, y-ová osa svírá s x-ovou 60 stupňový úhel. Například vrcholy jednoho z jednotkových trojúhelníků mají souřadnice (0,0), (1,0), (0,1).

V této síti zadáme N-úhelník - jeho vrcholy leží ve vrcholech sítě, jsou navzájem různé, přičemž každé dva sousední vrcholy v N-úhelníku mají jednotkovou vzdálenost. N-úhelník je zadán na vstupu tak, že první řádek vstupu obsahuje číslo N a dalších N řádků obsahuje souřadnice vrcholů, přičemž tyto vrcholy jsou zadány postupně po obvodu.

Napište a odlaďte program, který

Poznámka: Minimalizujte paměťovou a časovou složitost algoritmu. Můžete předpokládat, že vstupní data jsou zadána korektně.

P-I-2

Pro danou konstantu N (N je prvočíslo, např. 991) máme vyhrazeno N-prvkové celočíselné pole P s indexy 0 až N-1. Prvky pole jsou na začátku inicializovány na nulu. Do tohoto pole budeme postupně zařazovat L celočíselných hodnot (navzájem různých a různých od nuly), kde 2 < L < N, pomocí procedury zarad: procedure zarad(X:integer); var i:integer; begin i := (x div 10 + x mod 10) mod N; while P[i] <> 0 do i := (i+7) mod N; P[i] := x; end; Tato procedura nejprve ze zařazované hodnoty X vypočítá předpokládanou hodnotu indexu v poli P, a pokud je tento prvek pole již obsazen (je tam nenulová hodnota), postupně hledá nejbližší volnou pozici v poli (pole je přitom ``zacyklené'' - za posledním (N-1)-tým prvkem následuje nultý). Jestliže je při hledání volného místa nutné postupně prohlížet následující prvky, budeme tuto situaci nazývat kolize a budeme počítat počet vzniklých kolizí. Počet kolizí při zařazování j-té hodnoty budeme označovat K[j] (K[j] bude tedy rovno počtu průchodů cyklem while při zařazování j-té hodnoty), celkový počet kolizí označíme CK.

Navrhněte algoritmus, který pro daná tři čísla L, G a CK najde takovou vstupní posloupnost hodnot H (délky L), aby celkový počet kolizí pro tuto posloupnost byl CK a poslední hodnota byla H[L]=G, případně zjistí, že taková posloupnost neexistuje.

P-I-3

Máme kreslicí zařízení schopné kreslit různé obrázky. Jejich popis však musí být zadán ve speciálním tvaru (jako znakový řetězec):
Tuto posloupnost bude kreslicí zařízení interpretovat následovně:
Kreslicí pero je stále natočeno nějakým směrem (na začátku algoritmu na sever) a podle parametrů posloupnosti buď mění toto natočení, nebo se v aktuálním směru pohybuje dopředu nebo dozadu (kreslí čáru) podle toho, zda je tato vzdálenost kladná nebo záporná.

Například posloupnost [4[100 90]] nakreslí čtverec se stranou 100. (Všimněte si, že číselné parametry jsou oddělené mezerou.)

Napište a odlaďte program, který přečte vstupní posloupnost zadanou ve tvaru znakového řetězce a zinterpretuje ji na grafické ploše obrazovky. Můžete předpokládat, že vstupní posloupnost je zadána korektně, obsahuje jen celočíselné hodnoty a že řetězec není delší než 255 znaků.

P-I-4

Vytvořte D0L systém, jehož růstová funkce je:

  1. f(n) = 4

  2. f(n) = n

  3. f(n) = 3n+2

  4. f(n) = n2

  5. f(n) = kn3, kde k je libovolné přirozené číslo

D0L systémy

Abecedou nazýváme libovolnou konečnou neprázdnou množinu. Prvky této množiny nazýváme znaky. Konečnou posloupnost znaků z nějaké abecedy nazýváme slovo. Znaky označujeme zpravidla písmeny ze začátku abecedy (a, b, c, ...), slova písmeny z konce abecedy (u, v, w, ...) a abecedy velkými písmeny ( A, B, ...).

Délkou slova w rozumíme počet znaků, z nichž se slovo skládá, označujeme ji |w|. Zřetězením slov v=a1a2...an a u=b1b2...bm rozumíme slovo v*u=a1a2...anb1b2...bm. Množinu všech slov, která se dají vytvořit ze znaků abecedy A, označujeme A*. Tato množina obsahuje také prázdné slovo, t.j. slovo nulové délky, které označujeme _ .

Pravidlem nad abecedou A nazýváme uspořádanou dvojici (a,v), kde a je prkem A a v je prvkem A*. Pravidlo zapisujeme ve tvaru a -> v.

Deterministický Lindermayerův systém bez interakce (D0L systém) je uspořádaná trojice (A,P,w), kde

Takovýto D0L systém produkuje posloupnost slov w1, w2, w3, ..., která začíná axiomem a pokračuje vždy slovem, jenž dostaneme z předcházejícího slova současným nahrazením všech znaků za slova podle pravidel. Tedy Uvědomte si, že pro každý znak máme právě jedno pravidlo a tedy právě jedno slovo, kterým budeme tento znak nahrazovat. Posloupnost produkovaná D0L systémem je proto jednoznačně určena.

Růstovou funkcí D0L systému nazýváme takovou funkci f: N -> N0 (N={1,2,...}, N0={0,1,2,...}), která pro pořadí slova v posloupnosti produkované D0L systémem udává délku tohoto slova. Přesněji f(i)=|wi|.

Příklad

Poznámka: Při konstrukci D0L systému dáváme přednost takovým systémům, které mají co nejmenší počet pravidel.