Matematická olympiáda – kategorie P

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

sobota 27.1.1996

Úvodní pokyny

Na řešení úloh 2. kola MO-P máte 4 hodiny č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 je nutnou součástí řešení pouze v případě, je-li to v zadání výslovně uvedeno. 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-II-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

Napište program, který spočítá obsah zadaného N-úhelníka 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-II-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. V tomto poli máme uloženo M různých kladných čísel (M Prvky jsou v poli P uloženy tak, aby bylo možné použít funkci Vyhledej na zjištění, kde se v poli P nachází prvek X (funkce vrátí polohu prvku X v poli P, pokud se X v poli nachází, v opačném případě vrátí hodnotu -1):
function Vyhledej(X:integer):integer; var i:integer; begin i:=(X div 10 + X mod 10) mod N; while P[i]>X do i:=(i+7) mod N; if P[i]=X then Vyhledej:=i else Vyhledej:=-1; end; int vyhledej(int X) { int i; i=(X/10 + X%10)%N; while(P[i]>X) i=(i+7)%N; if(P[i]==X) return(i); else return(-1); }

Úloha

  1. Napište, jak musí být prvky uloženy v poli P, aby bylo možné k jejich vyhledávání použít funkci Vyhledej.

  2. Napište co nejefektivnější proceduru Zarad, pomocí níž bude možné zařadit prvek X do pole P tak, aby mohla být k vyhledávání použita funkce Vyhledej. Předpokládejte, že před použitím procedury Zarad byly prvky v poli P takto uspořádány a že prvek X se v poli P dosud nenachází.

P-II-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):
  • je to posloupnost parametrů uzavřená v závorkách []
  • parametrem je buď číslo, nebo opět posloupnost parametrů
  • posloupnost parametrů je vždy sudé délky, přičemž na lichých pozicích je vždy číslo
Tuto posloupnost bude kreslicí zařízení interpretovat následovně:
  • je-li posloupnost prázdná, nekreslí se nic
  • je-li neprázdná, zřejmě první parametr (P1) je číslo a druhý (P2) je buď číslo, nebo opět posloupnost parametrů
  • pokud je P2 číslo, kreslicí pero přejede (se spuštěným perem) v momentálním směru natočení vzdálenost P1 (všimněte si, že P1 může být i záporné, v takovém případě se kreslicí pero posune o danou vzdálenost opačným směrem) a potom se otočí o úhel P2 vpravo (úhel je zadán ve stupních)
  • pokud je P2 posloupnost, kreslicí zařízení P1-krát zopakuje posloupnost P2
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.)

Starší kreslicí zařízení obvykle mají rozsynchronizované ovládací obvody. Proto se stává, že často nakreslí místo čáry délky P čáru délky P+1 nebo P-1. V důsledku toho kreslicí pero obvykle skončí na jiném místě, než kde mělo skončit podle zadané posloupnosti.

Úloha

Nalezněte a dokažte algoritmus, který pro danou vstupní posloupnost (ve tvaru znakového řetězce) určí, jak nejdále může pero staršího kreslicího zařízení skončit od místa, kde mělo skončit podle zadané posloupnosti.

P-II-4

Vytvořte D0L systém (nebo dokažte, že to není možné), jehož růstová funkce je:
  1. f(n)=nn

  2. f(n)=n22n

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

  • 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
  • w1 = w
  • jestliže wi=a1a2...an, potom wi+1=u1*u2*...*un, kde aj -> uj 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 -> 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

  • {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, a3b, a7b, a15b, ...).
  • Růstová funkce tohoto D0L systému je f(n)=2n.
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.