Třetí série třináctého ročníku KSP

Zadání úloh

13-3-1 Hip hop (10 bodů)

Malý Vašek dostal k Vánocům hru Hip hop. Na hracím plánu k této hře je N významných bodů (budeme jim říkat „stanoviště“). Mezi těmito stanovišti vedou trasy rozdělené na políčka (z jednoho stanoviště mohou vést trasy do libovolně mnoha dalších stanoviť). Trasy se nikde mimo stanoviště nekříží.

Jednou z meziher hry Hip hop jsou takzvané „závody“. Ty probíhají tak, že se náhodně vybere počáteční a cílové stanoviště a hráči se pak musí co nejrychleji dostat z počátečního do cílového stanoviště. Přesun probíhá tak, že si v každém kole hráč hodí kostkou a může se posunout o tolik políček kupředu, kolik hodil.

Vaším úkolem je pomoci Vaškovi a napsat program, který dostane na vstupu popis herního plánu (tzn. počet stanovišť N, počet tras M a poté popis jednotlivých tras, přičemž každá trasa je popsána čísly dvou stanovišť, která propojuje, a počtem políček na ní) a počáteční a cílové stanoviště. Na výstup pak vypíše stanoviště na nejkratší cestě (délku cesty měříme počtem políček na ní) z počátečního do cílového stanoviště. Při řešení úlohy by vám ještě mohlo pomoci, že žádná trasa neobsahuje více než 12 políček.

Příklad: Mějme plán s pěti stanovišti a následujícími šesti trasami: 1–2 (1), 1–3 (5), 2–4 (4), 1–4 (7), 3–4 (2), 4–5 (3) (čísla v závorkách udávají počet políček na trase). Nejkratší cesta ze stanoviště 1 na stanoviště 5 vede 1→2→4→5.

Řešení

13-3-2 Fairies rights (11 bodů)

Společnost na ochranu tiskařských šotků se rozhodla zasáhnout proti diskriminaci skřítků pracujících v tiskařském průmyslu. Uvádíme úryvek z jejich prohlášení: "…kdjaký pisálek si klofá dp svého psacího strojw a každý druhý klof jde veddle. Pak se ani neobtěžuje po sobě text přečíst a chybh opravit. Když je již vše vytištěno a na chyby se přejde, tak se neprávem svádí na tiskřské šotky …"

Byla ustavena speciální komise na posuzování tiskařských chyb (SKoPoTiCH), která měla za úkol posoudit vliv šotků na množství chyb v textu. Komise vždy získala jednak výtisk nějakého textu a jednak autorův originál a měla zjistit množství chyb způsobených tiskařskými šotky. Tato práce se ukázala být značně namáhavá a pomalá. Proto se komise rozhodla využít výpočetní techniky a vymyslela důmyslný algoritmus automatického počítání počtu chyb.

Algoritmus se vlastně snaží jednoduchými úpravami převést text originálu na text výtisku. Pro každou úpravu je stanovena její „cena“ (nějaké kladné celé číslo) a algoritmus hledá takový převod, který je nejlevnější (tzn. součet cen jednotlivých úprav je minimální). Povolené úpravy jsou následující:

Protože však nikdo nedokázal algoritmus naimplementovat, byli jste požádáni o pomoc.

Vaším úkolem je napsat program, který dostane na vstupu ceny oněch tří povolených úprav a dva řetězce (originál a výtisk) a na výstup vypíše cenu nejlevnějšího převodu originálu na výtisk a poté samotný převod (tedy posloupnost úprav).

Příklad: Ceny:

Pro řetězce abcdefghi a abbcdfghj je cena nejlevnějšího převodu 10 a převod vypadá následovně: vypustit znak na pozici 3, vložit e za pozici 4, změnit znak na pozici 9 na i.

Řešení

13-3-3 Konvertor (10 bodů)

Pan Brouček se rozhodl si pro své výlety postavit vesmírnou loď (vždyť přece cestoval až na Měsíc a prý má plány vyrazit ještě dále). Už si sehnal rozličné součástky, jako třeba plasmový hypermotor, emitor mionů nebo prediktor chyb. Stále mu ovšem chybí Konvertor a nemůže ho nikde sehnat. A tak požádal vás, jestli byste mu nepomohli.

Konvertor je zařízení, které převádí číslo zapsané v jedné číselné soustavě na číslo zapsané v jiné soustavě. Není to ovšem tak jednoduché, protože základ soustavy může být i záporný.

Nadefinujme si čísla v soustavě o základu z, kde z je celé číslo a 2 ≤ |z|≤ 16. Každá cifra čísla je znak z intervalu 0, 1, … , |z|-1, kde předpokládáme, že číslu deset odpovídá znak a, číslu jedenáct znak b až číslu patnáct znak f. Hodnota čísla ckck-1… c0, kde ci pro 0 ≤ i ≤ k je i-tá cifra zleva, je pak ∑
k
i=0
cizi.

Pro bližší osvětlení uvedeme jako příklad soustavu o základu -2. Hodnoty jednotlivých řádů v této soustavě jsou (-2)0 = 1, (-2)1 = -2, (-2)2 = 4 … a cifry jsou buď 0 nebo 1. Tedy například číslo 9 má v minusdvojkové soustavě zápis 11001, protože 9 = 1*16 + 1*(-8) + 0*4 + 0*(-2) + 1*1.

Vaším úkolem je napsat program, který dostane na vstupu základ vstupní soustavy, základ výstupní soustavy a korektní číslo ve vstupní soustavě. Na výstup pak má vypsat dotyčné číslo převedené do výstupní soustavy (můžete předpokládat, že zadané číslo bude nezáporné, takže půjde vždy vyjádřit ve výstupní soustavě).

Příklad: Pro vstupní soustavu o základu -3, výstupní soustavu o základu 16 a číslo 11112 by měl program vypsat 3e.

Řešení

13-3-4 Šťastná čísla (10 bodů)

Pan Uno se zabývá numerologií. Při svých výzkumech přišel na to, že o šťastnosti čísla nerozhoduje ani tak jeho konkrétní hodnota, jako spíše jeho dělitelé. Po letech výzkumů pak došel k závěru, že šťastná jsou ta čísla, která jsou dělitelná pouze třemi, sedmi, jedenácti nebo libovolnými mocninami těchto čísel. Poté, co pan Uno došel k takto závažným výsledkům, je na vás, abyste je pomohli uvést do praxe (přeci jen zákazníci pana Uno chtějí slyšet konkrétní čísla a ne jen nějakou teorii). Vaším úkolem je tedy pro dané N vypsat prvních N šťasných čísel.

Příklad: Pro N=8 by program měl vypsat 3, 7, 9, 11, 21, 27, 33, 49.

Řešení

13-3-5 LISP (10 bodů)

Vaším dnešním úkolem bude naimplementovat funkce Map a BFS. Funkce Map dostane jako argumenty funkci beroucí jeden argument a seznam. Vrátit by měla seznam, jehož i-tý prvek je výsledek funkce zadané jako první argument na i-tý prvek původního seznamu.

Funkce BFS dostane jako argument binární strom a vrátí seznam prvků vzestupně seřazený podle vzdálenosti od kořene (tzn. v pořadí, v jakém vrcholy prochází prohledávání do šířky). Uzel stromu bude mít strukturu (hodnota . (levý syn . pravý syn)), pokud levý nebo pravý syn neexistují, je na jejich místě hodnota nil.

Příklad: (Map (lambda (x) (+ x 1)) (5 4 6 1)) by měl vrátit seznam (6 5 7 2), protože funkce daná jako první argument vrátí vždy dané číslo zvětšené o jedna.

Příklad: (BFS (1 . ((5 . (nil . nil)) . (3 . ((4 . (nil . nil)) . (6 . (nil . nil))))))) by mělo vrátit seznam (1 5 3 4 6).

Pokud si své programy chcete vyzkoušet, můžete si stáhnout interpret Ksp-Lispu (tar, ZIP).

Řešení