Úložky

Máte neznámou funkci f, která z celého čísla dělá celé číslo, a číslo a. Zajímáte se o hodnoty a,f(a),f(f(a)), atd. Máte zaručeno, že takto získané hodnoty se buď zacyklí, nebo se v nich objeví 0.

Navrhněte algoritmus, který zjistí, zda se hodnoty zacyklí, nebo zda se v nich objeví 0. Časová složitost musí být co nejmenší a paměti použijte jenom konstantně mnoho. [2 body]

Pokud se hodnoty zacyklí, nalezněte první hodnotu na cyklu, tj. první takové číslo, které se mezi zkoumanými hodnotami opakuje. Opět co nejmenší časová složitost a konstantní paměť. [2 body]

Dostanete N čísel a[1], a[2], …, a[N]. Vaším úkolem je v co nejlepším čase najít nejdelší souvislý úsek s nezáporným součtem (a pokud to nebude jasné, dokázat, že tento postup opravdu funguje).

Dostanete N nenulových čísel a[1], a[2], …, a[N]. Vaším úkolem je v co nejlepším čase najít nejdelší souvislý úsek se stejným počtem záporných a kladných prvků. Opět je třeba dokázat, že algoritmus opravdu funguje.

Dostanete N čísel a[1], a[2], …, a[N]. Vaším úkolem je v co nejlepším čase najít nejdelší rostoucí podposloupnost zadané posloupnosti. Opět okomentujte správnost algoritmu.

Popište, v jakém jazykovém jevu spočívá vtip následující básničky

Najděte co nejvíc smysluplných syntaktických rozborů této věty

(za 3 řešení 1 bod, za 5 řešení 2 body)

Vymyslete vlastní českou větu s neprojektivní konstrukcí.

Nakreslete složkový a závislostní syntaktický strom pro následující větu. Neterminální symboly si můžete vymyslet vlastní.

Vytvořte soubor délky 65536 bajtů takový, aby po zazipování byl co nejdelší. Program zip.exe můžete najít na sdíleném disku v adresáři ulozky a spouštějte ho s parametry zip.exe -9 out.zip vstupní_soubor. Název vašeho souboru musí být pouze první čtyři písmena vašeho příjmení.

Napište klienta hrajícího „Bomber mana“. Podrobnosti u Tomáše & Tomáše.

Napište program, který zajistí zajímavý pohyb grafického objektu po obrazovce za využití spritů na platformě Commodore 64 Basic. Vlastní grafická data výhodou.

Na vstupu dostanete N a trojúhelníkovou pyramidu o N řádkách, i-tý obsahuje i čísel. Vaším úkolem je najít cestu z vrcholu pyramidy na její spodek s největším součtem čísel na ní. Výstupem vašeho programu má být jen součet čísel na nejdražší cestě, cestu samotnou vypisovat nemusíte. Nejlepší řešení má složitost O(N^2).

Na vstupu dostanete N, čísla a[1], a[2], ..., a[N] a číslo K. Vaším úkolem je zjistit, zda zadaná posloupnost obsahuje souvislý úsek se součtem K.

Dostanete bludiště o rozměrech N krát M, pozici Thésea, Minotaura a východu. Vaším úkolem je najít nejkratší cestu Thésea z bludiště tak, aby ho Minotaurus nesežral. Théseus se pohybuje v jednom tahu do čtyř směrů, Minotaurus se pohybuje v jednom tahu dvakrát podle následujícího pravidla: pokud není Minotaurus ve stejném sloupci jako Théseus, snaží se do něj dostat (pokud mu v cestě stojí zeď, čeká), pokud je Minotaurus ve stejném sloupci jako Théseus, snaží se dostat do stejného řádku.

Drak si myslí číslo 0 až 1 000 000, vaším úkolem je ho uhodnout. V jednom tahu můžete drakovi dát seznam čísel v rozsahu 0 až 1 000 000 a drak vám odpoví, zda je jeho tajné číslo na vašem seznamu. Drak ovšem může (ale nemusí) v celé hře jednou zalhat. Váš algoritmus musí fungovat spolehlivě, ať už drak zalhal nebo ne, a čím méně dotazů použijete, tím lépe. Existuje řešení s 26 dotazy v nejhorším případě.

Probíhají volby a volí se jeden z K kandidátů. Dostali jste N hlasů (každý hlas je číslo kandidáta 1 až K) a chcete vědět, zda někdo získá nadpoloviční většinu hlasů. Paměťová složitost musí být konstantní.

Dostanete neprotínající se mnohoúhelník definovaný pomocí N bodů na jeho obvodu. Spočtěte co nejrychleji jeho obsah.

Napište program, který v zadaném textu najde pomocí internetového vyhledávače věty, které jsou zkopírované z nějaké již existující stránky. Výsledkem bude HTML stránka, kde v původním textu budou jinde nalezené věty sloužit jako odkaz na stránku, kde se již vyskytly.