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)=n², nebo dokažte, že takový systém neexistuje.

2. Sestrojte D0L systém s růstovou funkcí f(n)=[log_k+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=a₁a₂...a_n a u=b₁b₂...b_m rozumíme slovo v*u=a₁a₂...a_nb₁b₂...b_m. 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

• A je abeceda
• P je množina pravidel, která pro každý znak a z abecedy A obsahuje právě jedno pravidlo nad abecedou A tvaru a -> u
• w je slovo ze A, které nazýváme axiom

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

• w₁ = w
• jestliže w_i=a₁a₂...a_n, potom w_i+1=u₁*u₂*...*u_n, kde a_j -> u_j jsou pravidla z množiny pravidel P pro j=1,2,...,n

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 -> N₀ (N={1,2,...}, N₀={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)=|w_i|.

Příklad

• {a,b} je abeceda obsahující dva znaky: a a b.
• Délka slova aabab je 5.
• Zřetězením slov ab a aab je slovo ab*aab=abaab.
• Nad touto abecedou můžeme vytvořit nekonečně mnoho slov: _, a, b, aa, ab, bb, aaa, ...
• Pravidlem je například a -> aa.
• D0L systémem je například ({a,b}, {a -> aa,b -> ab}, ab).
• Posloupnost produkovaná tímto systémem je
  ab, aaab, aaaaaaab, aaaaaaaaaaaaaaab, ...
  (Když slovo obsahuje více stejných písmen za sebou, můžeme nahradit tato písmena jedním písmenem, u kterého uvedeme počet písmen, která zastupuje. Zkráceně můžeme tedy psát posloupnost tohoto D0L systému: ab, a³b, a⁷b, a¹⁵b, ...).
• Růstová funkce tohoto D0L systému je f(n)=2ⁿ.

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.