Matematická olympiáda – kategorie P

Zadání úloh školní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):

• popis řešení, to znamená popis použitého algoritmu, zdůvodění správnosti vašeho řešení (případně důkaz algoritmu), diskusi o efektivitě zvoleného řešení apod. Důležité je, aby byl popis řešení jasný a srozumitelný i bez toho, že bylo třeba nahlédnout do samotného programu.
• program je nutnou součástí řešení v případě, že to zadání úlohy vyžaduje (tedy v prvním a třetím příkladu). Program může být napsán buď v jazyce Pascal, nebo v jazyce C. Program je nutno odevzdat v písemné formě a také na disketě, aby bylo možné otestovat jeho funkčnost. Na jedné disketě odevzdávejte program vždy jen k jednomu řešení. Není tedy možné na stejné disketě odevzdat řešení prvního i třetího příkladu. V rámci školy je ale možné domluvit, že řešení téhož příkladu od více řešitelů budou zaslána společně na jedné disketě (v tom případě je však třeba důkladně rozlišit jednotlivé řešitele, nejlépe pomocí názvů podadresářů).

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ý

• vykreslí tento N-úhelník na obrazovku
• vypíše zprávu o tom, zda je konvexní nebo ne (N-úhelník je konvexní, jestliže úsečky spojující libovolné dva vrcholy leží celé uvnitř, resp. na hranici N-úhelníka.)

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

Navrhněte algoritmus, který pro daná tři čísla L, G a C_K najde takovou vstupní posloupnost hodnot H (délky L), aby celkový počet kolizí pro tuto posloupnost byl C_K 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):

• je to posloupnost parametrů uzavřená v '[' a ']' 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 (P₁) je číslo a druhý (P₂) je buď číslo, nebo opět posloupnost parametrů:
  
  • pokud je P₂ číslo, kreslicí pero přejde (se spuštěným perem) v momentálním směru natočení vzdálenost P₁ a potom se otočí o úhel P₂ vpravo (úhel je zadán ve stupních)
  • pokud je P₂ posloupnost, kreslicí zařízení P₁-krát zopakuje posloupnost P₂

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) = n²

5. f(n) = kn³, 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=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.