Matematická olympiáda – kategorie P

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

Řešení každého příkladu musí obsahovat podrobný popis použitého algoritmu, zdůvodnění jeho správnosti a diskusi o efektivitě zvoleného řešení (tzn. posouzení časových a paměťových nároků programu).

V praktických úlohách P-I-1 a P-I-3 je třeba k řešení připojit odladěný program zapsaný v jazyce Pascal, C nebo C++. Program se odevzdává v písemné formě (jeho výpis je tedy součástí řešení) i na disketě, aby bylo možné otestovat jeho funkčnost. Slovní popis řešení musí být ovšem jasný a srozumitelný, aniž by bylo nutno nahlédnout do zdrojového textu programu. V úloze P-I-2 se odladěný program nepožaduje, stačí uvést dostatečně podrobný zápis algoritmu. V úloze P-I-4 zapište navržený algoritmus ve formě reverzibilní procedury.

Řešení úloh domácího kola MO kategorie P vypracujte a odevzdejte nejpozději do 15. 11. 2002. Vzorová řešení úloh naleznete po tomto datu na Internetu na adrese http://mo.mff.cuni.cz. Na stejném místě jsou stále k dispozici veškeré aktuální informace o soutěži a také archív soutěžních úloh a výsledků minulých ročníků.

P-I-1 Čajovník

Pan Nyi byl dvorním pěstitelem čaje císaře Tiang-tonga. Byl to pěstitel skutečně vyhlášený a jeho čajové lístky putovaly nejen do blízkých šálků císaře Tianga, ale i do dalekých zemí za oceánem. Tajemství Nyiho skvělého čaje spočívalo především v pečlivosti, s jakou se o své čajové keře staral. Nyi byl tak pečlivý, že si o každém svém keři vedl záznamy. Psal si dokonce i to, kolik větviček vychází z kterého místa keře. Po smrti pana Nyiho byly záznamy rozkradeny a jeho nástupce pan Myi tak měl práci o mnoho těžší. Rozhodl se proto, že záznamy získá zpět. Problémem ale je, že mnoho různých podvodníků mu nabízí záznamy falešné. Ty naštěstí většinou obsahují nesmyslné počty větvení, a tak se dají snadno odhalit. Pana Myiho neustálé ověřování pravosti záznamů už unavuje, a proto vás požádal, abyste mu napsali program, který mu s ověřováním pomůže.

Čajovník
Váš program dostane na vstupu počet významných míst N na údajném čajovníku. Významným místem na čajovníku je buď místo, kde se čajovník větví, nebo místo, kde končí nějaká větev čajovníku. Protože žádné dvě větve čajovníku nemohou srůstat, nemohou vznikat "cykly" z větví. Dále je na vstupu programu zadáno N kladných celých čísel c1, c2, ..., cN, kde ci určuje počet částí kmene, které vycházejí z i-tého významného místa. Na výstup program vypíše zprávu, zda může existovat čajovník, který bude mít takovéto počty větvení.

Formát vstupu

Vstupní textový soubor caj.in obsahuje dva řádky. Na prvním řádku je uvedeno jediné celé číslo N, 1<=N<=1000. Druhý řádek obsahuje celá čísla c1, c2, ..., cN oddělená mezerami, 1<=ci<=N-1.

Formát výstupu

Výstupní textový soubor caj.out obsahuje jediný řádek tvořený buď slovem EXISTUJE nebo slovem NEEXISTUJE.

Příklad 1

Soubor caj.in:
14 1 4 3 1 1 3 1 1 3 1 4 1 1 1 Soubor caj.out:
EXISTUJE

Příklad 2

Soubor caj.in:
6 3 3 3 1 1 1 Soubor caj.out:
NEEXISTUJE

P-I-2 Knihovna

Knihovnice Míla potřebuje objednat další skříň s poličkami do své knihovny; bohužel však sama neumí spočítat její optimální rozměry. Míla by ráda do nové skříně umístila N knih. Každá kniha má přiřazen jednoznačný číselný kód a tyto kódy určují pořadí knih ve skříni. Kniha s menším kódem se má nacházet na stejné nebo výše umístěné poličce než kniha s větším kódem; na každé poličce mají být knihy s menšími kódy umístěny vlevo od knih s většími kódy. Vstupem vašeho programu bude posloupnost N čísel vi, 1<=i<=N, kde vi je výška i-té knihy (uspořádáno podle rostoucích kódů). Pro zjednodušení můžete předpokládat, že všechny knihy mají stejnou tloušťku 1 cm. Váš program by měl ze zadaných údaju spočítat následující: Navíc si knihovnice Míla přeje, aby skříň byla co nejužší a přitom aby se vešla do místnosti vysoké 250 cm. Rozmístění knih, které váš program nalezne, musí tedy ještě splňovat následující podmínky:

Příklad

Předpokládejme, že Míla chce do skříně umístit celkem 11 knih, jejichž výšky jsou v pořadí podle jejich kódů následující: 40 cm, 10 cm, 40 cm, 25 cm, 40 cm, 25 cm, 50 cm, 40 cm, 40 cm, 25 cm a 40 cm. Jedno z optimálních řešení by mohlo vypadat následovně: Skříň bude mít šířku pro 3 knihy a celkem 4 poličky s následujícími výškami: 40 cm, 40 cm, 50 cm a 40 cm. Výška skříně je v tomto případě 175 cm. Nalezení jednoho konkrétního možného umístění knih do skříně je snadné.

P-I-3 Transformace

Jedna z metod zpracování textu používá následující transformační algoritmus:
Na vstupu mějme n-znakový řetězec C=c1c2...cn, jehož všechny znaky jsou navzájem různé. Řetězec C'=ck+1ck+2...cnc1... ck nazýváme řetězcem C zrotovaným o k (tedy např. eldat je řetězec datel zrotovaný o 3). Vezměme si zadaný řetězec C a napišme si pod sebe C, C zrotovaný o 1,...,C zrotovaný o n-1. Tím jsme získali tabulku n řetězců. Ty setřídíme v běžném lexikografickém pořadí (tzn. podle abecedy). Z výsledné tabulky si vybereme poslední sloupec S; dále si také zapamatujeme číslo řádku ř, na němž se po setřídění nachází náš původní řetězec. Dvojice (S,ř) je výsledek transformace zadaného vstupu. Jakkoli magicky to vypadá, tyto dva údaje stačí k rekonstrukci původního řetězce.

Příklad

Na vstupu máme slovo datel. Transformace probíhá takto:
datel    ateld
ateld    datel
telda -> eldat
eldat    ldate
ldate    telda
Výsledkem tedy je slovo dltea a informace, že původně zadané slovo je na druhém řádku setříděné tabulky.

Soutěžní úloha

Program dostane na vstupu řetězec S délky n (1<=n<=100), jehož všechny znaky jsou navzájem různé (tj. je-li S=s1s2... sn, pak si<>sj pro každá i, j, i<>j), a číslo ř (1<=ř<=n). Úkolem je najít řetězec C takový, že dvojice (S,ř) je výsledkem aplikace výše popsané transformace na řetězec C (máte zaručeno, že takový existuje).

Uvědomte si, že při použití v praxi se délky zpracovávaných vstupů pohybují řádově ve stovkách kilobytů; je tedy nevhodné, aby váš program měl kvadratické časové nebo paměťové nároky.

Formát vstupu

Na prvním řádku vstupního souboru bw.in se nachází řetězec S (řetězec neobsahuje mezery). Na druhém řádku je jedno celé číslo ř.

Formát výstupu

Výstupní soubor bw.out je tvořen jedním řádkem, obsahujícícím řetězec C (jehož transformací je dvojice (S,ř)).

Příklad

Soubor bw.in:
dltea 2 Soubor bw.out:
datel

P-I-4 Reverzibilní výpočty: Políčko pole

Při hledání nových, úspornějších polovodičových technologií se zjistilo, že nejvíce energie se spotřebovává při mazání informací, tudíž že optimální jsou ty výpočty, při nichž se žádné informace neztrácejí. Takovým výpočtům se říká reverzibilní, protože díky této vlastnosti mohou probíhat oběma směry - dokáží nejen spočítat ze vstupu výstup, ale také z výstupu jednoznačně určit vstup. Vydejme se proto i my do tohoto zvláštního symetrického světa a prozkoumejme, jak se programuje "ekologicky".

Začněme tím nejjednodušším, co se v klasických programovacích jazycích vyskytuje, a to je přiřazovací příkaz. Nic takového si bohužel dovolit nemůžeme, ztratili bychom totiž původní obsah proměnné, do níž se přiřazuje. Místo toho zavedeme několik příkazů modifikujících proměnnou vratně:

Abychom se vyhnuli problémům s přetečením (co by pak byla inverzní operace?), dohodněme se, že budeme počítat pouze s nezápornými celými čísly v rozsahu 0... maxword (takovým číslům budeme říkat přirozená) a všechny operace budou vydávat výsledky modulo maxword+1, tedy opět přirozené číslo. Příkaz += provedený pozpátku je pak totéž, co -= a opačně; přikazy ^= a =:= jsou inverzní samy k sobě.

Co všechno ale může být hodnota? Jistě libovolná konstanta nebo proměnná (ovšem různá od té, do které přiřazujeme, jinak bychom mohli napsat třeba a -= a, což určitě reverzibilní není). Také bychom měli povolit nějaké další aritmetické operace - ty samy nemusí být reverzibilní, důležité je, aby se jejich výsledek zpracoval reverzibilně. Každý složitější výraz pak už můžeme přepsat na výrazy s jedinou operací, například x^=(a*b)+(c*d) rozepíšeme takto:

t1 += a*b; t2 += c*d; x ^= t1+t2; t2 -= c*d; t1 -= a*b; Zde t1 a t2 jsou pomocné proměnné, které jsou na počátku výpočtu nulové a po dopočítání výrazu se opět k nulovým hodnotám vrátí, takže je můžeme používat pro všechny výrazy v celém programu. Podobně se vypořádáme s každým výrazem - nejdříve si spočítáme všechny mezivýsledky do pomocných proměnných, pak hlavní výsledek použijeme, načež mezivýsledky opět "odpočítáme". Takže můžeme používat i slozité výrazy a spolehnout se na překladač, že je sám rozepíše. Trik s odpočítáváním mezivýsledků a spouštěním částí programu pozadu je, zdá se, velice šikovný, tak si rovnou nadefinujeme, že undo příkaz znamená spustit příkaz pozpátku a wrap příkaz1 on příkaz2 provede nejdříve příkaz1, pak příkaz2 a nakonec undo příkaz1 pro odpočítání mezivýsledků. Náš příklad s výrazem pak snadno zapíšeme takto: wrap begin t1 += a*b; t2 += c*d end on x ^= t1+t2 Podmíněné příkazy if-then-else můžeme používat bez obav, pokud zaručíme, že po provedení podmíněného příkazu dopadne podmínka úplně stejně jako předtím (třeba proto, že žádná z proměnných, které v ní vystupují, není v podmíněné části programu měněna). Pak totiž i při provádění výpočtu pozpátku rozpoznáme, kterou z větví se výpočet má vydat.

S cykly je situace svízelnější, protože tam si s neměnícími se podmínkami nevystačíme (to by každý cyklus buďto neproběhl nikdy nebo by se opakoval do nekonečna). Dalo by se to, pravda, zachránit tím, že by každý cyklus měl jednu podmínku, která by fungovala současně jako vstupní i výstupní - sami si rozmyslete, jak by takové cykly vypadaly. My si ale pro naše účely vystačíme s cykly for, ty určitě reverzibilní jsou, pokud řídící proměnnou cyklu ani její meze žádný příkaz uvnitř cyklu nemodifikuje, a to se koneckonců nesmí ani v mnoha jiných programovacích jazycích. Navíc abychom nemuseli řešit, co se v řídící proměnné musí vyskytovat před začátkem cyklu a co po jeho konci, domluvíme se, že příkaz for si tuto proměnnou sám vytvoří a na konci ji zase zruší.

Příkaz goto pro jistotu zakážeme úplně.

Procedury mohou také fungovat reverzibilně, ale musíme se vyhnout kopírování parametrů a výsledků, budeme proto vše vždy předávat odkazem (pascalské var). Lokální proměnné budou při spuštění procedury vždy nulové a procedura sama je musí, než skončí, opět do tohoto stavu vrátit. Rekurze je bez problémů.

Nyní již máme vše potřebné, abychom si vybudovali reverzibilní programovací jazyk. Ten náš bude vzdáleným příbuzným Pascalu. Vypadá takto:

Příklad 1

Procedura pro prohození obsahu dvou proměnných (která ukazuje, že =:= se dá snadno odvodit pomocí ostatních operací). Časová i prostorová složitost jsou konstantní, tedy O(1). procedure Prohod(var x,y:word); begin { x = X, y = Y (X,Y jsou pův. hodnoty) } x ^= y; { x = X xor Y, y = Y } y ^= x; { x = X xor Y, y = Y xor (X xor Y) = X } x ^= y { x = (X xor Y) xor X = Y, y = X } end;

Příklad 2

Procedura pro výpočet maxima ze zadaných n čísel. Je dáno pole X celých čísel a proměnná max, k níž máme spočtené maximum přičíst. To dokážeme takto: Nejprve si předpočítáme do M[i] maximum z čísel X[1],...,X[i], pak přičteme M[n] k max a nakonec M[i] opět vyprázdníme, což snadno zapíšeme pomocí příkazu wrap. Časová i prostorová složitost jsou O(n) čili lineární. procedure Maximum(var n:word; var X:array [1..n] of word; var max:word); var M:array [0..n] of word; begin wrap for var i=1 to n do if X[i]>M[i-1] then M[i] += X[i] else M[i] += M[i-1] on max += M[n]; end;

Soutěžní úloha

Napište reverzibilní proceduru Najdi(var n: word; var X: array[1..n] of word; var co, kde: word). Tato procedura má za úkol v n-prvkovém poli X hledat hodnotu co a pokud se tam tato hodnota vyskytuje, přičíst k proměnné kde pozici jejího výskytu, tedy i takové, že Xi=co. Navíc je známo, že pole X je uspořádáno vzestupně, tedy že pro každé i<j platí Xi<Xj; proto také může být výskyt nejvýše jeden. Ve svém řešení se snažte dosáhnout co nejmenší časové i prostorové složitosti.