Matematická olympiáda – kategorie P

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

Bílovec, 25.4.1996

Úvodní pokyny

Na řešení úloh prvního soutěžního dne celostátního kola MO-P máte 5 hodin čistého času. Řešení každého příkladu musí obsahovat (není-li uvedeno jinak) popis použitého algoritmu, zdůvodnění jeho správnosti, diskusi o efektivitě vašeho řešení apod. Důležité je, aby byl popis řešení jasný a srozumitelný i bez nutnosti nahlížet do programu.

Program není nutnou součástí řešení, je však vhodnou formou zápisu vašeho algoritmu. Program může být napsán buď v jazyce Pascal nebo v jazyce C. Program nemusí realizovat všechny části řešení. Zejména je možné vynechat ty části, které zabezpečují vstupy, výstupy a jednoduché operace (např. operace s množinami, implementaci jednoduchých geometrických vztahů apod.).

P-III-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 60stupň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.

Úloha

Na vstupu je zadán N-úhelník a M-úhelník. Napište program, který spočítá obsah jejich průniku a vyjádří ho počtem jednotkových trojúhelníků.

Poznámka

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

P-III-2

Pro danou konstantu N (N je prvočíslo větší než 10, např. 991) máme vyhrazeno N-prvkové celočíselné pole P s indexy 0 až N-1. Prvky pole jsou na začátku výpočtu inicializovány na nulu. Do tohoto pole budeme postupně zařazovat různá kladná celá čísla pomocí procedury Zarad:
procedure Zarad(x:integer); var i:integer; begin i := x mod N; while P[i] <> 0 do if P[i]>x then i := (i+7) mod N else i := (i+3) mod N; P[i] := x; end; void zarad(int x) { int i; i = x % N; while (P[i]!=0) { if (P[i]>x) i = (i+7) % N; else i = (i+3) % N; } P[i] = x; }

Úloha

  1. Napište co nejefektivnější funkci Vyhledej s jedním celočíselným parametrem x, která zjistí, zda se prvek x nachází v poli P. Pokud ano, funkce vrátí hodnotu indexu prvku x v poli P. Jestliže číslo x v poli P není, funkce vrátí hodnotu -1.

  2. Rozhodněte, zda je výpočet procedury Zarad v případě, že je v poli P alespoň jedno volné místo (tj. aspoň jeden prvek pole P má hodnotu 0), vždy konečný. Odpověď dokažte.

P-III-3

  1. Sestrojte D0L systém s nejvýše dvěma pravidly, jehož růstová funkce je f(n)=n2, nebo dokažte, že takový systém neexistuje.

  2. Sestrojte D0L systém s růstovou funkcí f(n)=[logk+1(n+1)]+1, kde k je počet symbolů abecedy, nebo dokažte, že takový systém neexistuje.

Poznámka

Zápisem [X] rozumíme dolní celou část z hodnoty výrazu X, tzn. hodnotu výrazu X zaokrouhlenou dolů na nejbližší celé číslo. Například [4.789]=4, [5]=5.

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.