První série patnáctého ročníku KSP

Zadání úloh

15-1-1 Narozeninový dort (11 bodů)

Manželé Terciovi měli trojčata – Alfíka, Betynku a Gamíka. Narozeniny byly pro rodiče vždy velmi náročné. Přeci jen shánět dárky hned pro tři děti naráz dá dost práce, a tak se rodiče jednoho roku rozhodli, že si alespoň trochu ulehčí práci a dají dětem dohromady jeden dort. Dort to nebyl ledajaký – měl tvar rovnostranného trojúhelníka a na dortu bylo tolik svíček, kolik měly děti dohromady let. Problém ale nastal, když se dort měl dělit. Každé dítě totiž chtělo mít tolik svíček, kolik mu právem náleží, a svíčky na dortu přitom byly rozmístěny náhodně. Tatínek se pokoušel dort rozdělit, ale brzy zjistil, že splnit požadavek dětí není tak jednoduché, a tak o pomoc požádal vás.

Vaším úkolem je navrhnout algoritmus a napsat program, který dostane na vstupu délku hrany dortu d (rohy dortu mají souřadice [0,0], [d,0], [d/2, d·√3/2]), počet svíček na dortu N (pochopitelně dělitelný třemi) a souřadnice jednotlivých svíček a nalezne na dortu bod takový, že řezy z jednotlivých rohů do nalezeného bodu rozdělí dort na tři části obsahující stejný počet svíček.

Příklad: Pro dort o délce hrany 10 a souřadnicích 3 svíček (1,1), (9,1) a (5,1) je hledaným bodem například bod o souřadnicích (5,3).

Řešení

15-1-2 Vláčky (11 bodů)

Vlastík měl doma postaveno velké kolejiště. Na kolejišti vedlo vedle sebe několik kolejí, které se mezi sebou složitě proplétaly (Vlastík při stavbě nešetřil ani nadjezdy a tunely), spojovaly se a zase se dělily. Jednoho dne Vlastíka napadlo spočítat, kolik vlaků může na kolejiště vypustit současně. Po chvilce zjistil, že problém to není vůbec jednoduchý, a tak se rozhodl si při řešení úlohy pomoci programem. Pomůžete mu s ním?

Vaším úkolem je navrhnout algoritmus a napsat program, který dostane na vstupu popis kolejiště a na výstup vypíše maximální možný počet tras, které se navzájem neprotínají (tzn. nemají žádný společný bod), spolu s jejich popisem. Kolejiště se skládá z N kontrolních bodů. i-tým kontrolním bodem vede ki kolejí. Dále je dán seznam kolejí mezi jednotlivými kontrolními body – j-té propojení mezi dvěma kolejemi v kontrolních bodech je popsáno dvěma dvojicemi (aj, bj), (cj, dj), kde aj a cj jsou čísla kontrolních bodů, mezi kterými kolej vede (předpokládejte, že cj=aj+1) a bj a dj jsou čísla kolejí v jednotlivých kontrolních bodech. Protože v kontrolních bodech se mohou vyskytovat výhybky, může být na jednu kolej v kontrolním bodě napojeno hned několik kolejí v předcházejícím a následujícím kontrolním bodě (ale nemusí být napojena kolej žádná). Předpokládejte, že koleje se stýkají či dělí pouze v kontrolních bodech a mezi body se koleje neprotínají (to ovšem neznamená, že jedna kolej nepřejíždí druhou po nadjezdu).

Příklad: Pro kolejiště se třemi kontrolními stanovištěmi se 4, 3 a 5 body a s propojeními (1,1)→(2,1), (1,1)→(2,2), (1,2)→(2,3), (1,3)→(2,2), (1,4)→(2,3), (2,1)→(3,1), (2,2)→(3,2), (2,2)→(3,4), (2,3)→(3,3) a (2,3)→(3,5) existují tři neprotínající se trasy. Jsou to například (1,1)→(2,1)→(3,1), (1,2)→(2,3)→(3,3) a (1,3)→(2,2)→(3,2).

Kolejiště s vyznačenými trasami
Kolejiště s vyznačenými trasami

Řešení

15-1-3 Kulový blesk (10 bodů)

Stěhovací firma Popruh a spol. se rozhodla uspořádat propagační akci Kulový blesk. Akce spočívá v tom, že N rodin si vymění byty takovým způsobem, že pokud rodina bydlela v bytě i, tak po stěhování bude bydlet v bytě i+1 (pokud rodina bydlela v bytě N, tak bude po stěhování bydlet v bytě 1). Zorganizovat takovou směnu je samozřejmě velmi náročné, a tak se firma rozhodla ji trochu zjednodušit. Výměna bude probíhat tak, že se dohodnou vždy dvojice rodin a ty si vymění byty (současně může probíhat libovolně takovýchto výměn najednou, ale každá rodina se v daném okamžiku může účastnit nejvýše jedné směny). Tento způsob má ale tu nevýhodu, že některé rodiny se budou muset stěhovat vícekrát, než se dostanou do kýženého cílového bytu. Protože celou výměnu by bylo vhodné provést v jeden den, chce pan Popruh v rámci zachování dobrého jména firmy minimalizovat dobu nutnou na stěhování. Nakonec se rozhodl obrátit na vás, abyste mu se svou znalostí programování pomohli naplánovat výměny bytů.

Váš program dostane na vstupu počet bytů N. Stěhování, které má program navrhnout, má probíhat tak, že v jednom okamžiku si vždy nějaké dvojice rodin vymění byty (jeden takovýto okamžik záměny nazveme „fází“). Váš program by tedy měl vypsat počet fází a pro každou fázi seznam dvojic bytů, které jsou v této fázi směněny. Navržené stěhování by mělo mít nejmenší možný počet fází.

Příklad: Pro čtyři rodiny lze stěhování provést na dvě fáze. V první fázi se vymění rodiny v bytech (1,2) a (3,4) a ve druhé fázi rodiny v bytech (1,3).

Řešení

15-1-4 Soustavy (8 bodů)

Vaším úkolem v této úloze je navrhnout algoritmus a napsat program, který dostane na vstupu tři čísla (či spíše řetězce složené ze znaků 0 až 9 a a až z) A, B a C a určí základ soustavy, ve které platí rovnice A+B=C. Pokud základ soustavy není jednoznačně určen, vypište soustavu s nejmenším základem, která rovnici vyhovuje.

Příklad: Pro A=1, B=1a a C=20 je základ soustavy 11.

Řešení

15-1-5 Haskell (10 bodů)

V letošní sérii se budeme zabývat funkcionálním programováním. Cílem je zejména vyvrátit obecně rozšířenou představu, že funkcionální programování = LISP = umění správně spočítat závorky. Pro účely výkladu (a také úloh pro vás) budeme používat programovací jazyk Haskell. Jedná se o poměrně komplikovaný jazyk a není v našich možnostech probrat ho celý; v následujícím textu si vyložíme alespoň jeho základy.

Pro řešení semináře by vám měl postačovat interpreter Hugs (http://www.haskell.org/hugs/). Pokud byste chtěli v Haskellu sepsat nějaký seriózní program, existuje kompilátor GHC (http://www.haskell.org/ghc/). Kompletní specifikaci jazyka si můžete přečíst například na http://www.haskell.org/definition/. Jsem ovšem v pokušení vypsat prémiové body za její pochopení.

Haskell je čistě funkcionální typovaný líně vyhodnocovaný jazyk. Co to všechno znamená?

Nyní se podívejme podrobněji na systém typů. Asi nejjednodušší bude začít příkladem:

data List x = Cons x (List x) |
              Nil

Tato definice deklaruje typ List x, což je seznam prvků typu x. Seznam je tedy buď prázdný (konstanta Nil), nebo je to dvojice, jejíž první prvek je typu x (tj. první prvek seznamu) a druhý prvek je seznam prvků typu x (zbytek seznamu). Například seznam 1, 2, 3 je vyjádřen jako Cons 1 (Cons 2 (Cons 3 Nil)). Cons a Nil jsou konstruktory; tedy funkce, které vytváří hodnoty daného typu. Cons má za argumenty hlavu a tělo seznamu, zatímco Nil je funkce bez argumentů (tedy konstanta).

Věci, které stojí za povšimnutí:

Haskell má některé základní typy:

Zbývá ukázat, jak vypadají typy funkcí. Funkce, která má jeden parametr typu a a vrací hodnotu typu b, má typ a->b. Logická otázka je, co s funkcemi více parametrů. Odpověd je, že si vystačíme s funkcemi s jedním argumentem. Například plus má typ Int->(Int->Int) – je to tedy funkce, která vrací funkci, která vrací Int. plus 5 je tedy funkce typu Int->Int (která vrací argument zvětšený o 5), a (plus 5) 10 je 15. Typy funkcí se závorkují vždy zprava, zatímco jejich aplikace zleva – tedy závorky v uvedeném příkladu jsou zbytečné, plus má typ Int->Int->Int a pro jeho vyhodnocení stačí napsat plus 5 10. Pozor – funkce jsou hodnoty jako každé jiné (je možné je dávat jako parametry jiným funkcím, je možné mít typ [a->b] – seznam funkcí, atd.)

Typy funkcí není potřeba uvádět – překladač si je domyslí. Je ovšem rozumné to dělat (snáze se pak odhalí chyby). Deklarace typu funkce vypadá takto:

length :: [a]->Int

Jak jsme již viděli na příkladech, program v Haskellu je množina rovností definujících funkce. Na konci zadání si můžete prohlédnou rozsáhlejší příklad demonstrující podmnožinu Haskellu nutnou pro rozumnou práci.

Několik poznámek k programům:

Nyní si uvedeme ještě několik užitečných funkcí definovaných ve standardní knihovně. U funkcí uvádíme i jejich typy (pro zjednodušení většinou jinak, než jak jsou skutečně definované):

A nyní již úlohy pro vás. Mějme typ pro strom definovaný takto:

data Tree a = Tree a [Tree a] deriving (Show)

Tedy strom prvků typu a obsahuje hodnotu typu a a seznam svých synů, což jsou opět stromy téhož typu (klauzule deriving Show zajistí, že překladač Haskellu bude umět hodnoty tohoto typu zobrazovat).

Příklad rozsáhlejších programů v Haskellu

delka::[x]->Int               - - délka seznamu
delka [] = 0                  - - délka prázdného seznamu je 0
delka (h:t) = delka t + 1     - - délka seznamu je jeho délka po odtržení
                              - -  prvního prvku + 1
 
delka_listu::List x->Int      - - totéž, ale pro námi definovaný typ List
delka_listu Nil = 0
delka_listu (Cons h t) = delka_listu t + 1
 
obrat::[a]->[a]               - - obrácení seznamu
obrat l = obrat' l []         - - vyvoláme pomocnou fci obrat'; obrat' l1 kon
 where                        - -  vrací obrácený seznam l1, za nějž připojí kon
  obrat' [] kon = kon         - - je-li l1 prázdný, vrať kon
  obrat' (h:t) kon = obrat' t (h:kon)
                              - - jinak obrať tělo l1, za něj připoj jeho hlavu
                              - -  a kon
 
radky :: String -> [String]   - - rozdělí řetězec na řádky (oddělené znakem '\n')
radky "" =  []                - - prázdný řetězec nemá řádky
radky s =  let (l, s') = sekni s - - jinak rozsekni s na prvním znaku '\n' (pomocnou
                              - - fcí sekni); první řádek dej do l, zbytek do s'
             in  l : case s' of  
                              - - vrať první řádek, za který připoj
                       ""         -> []
                              - -  nic, pokud uz nic nezbýva
                       ('\n':s'') -> radky s''
                              - -  ostatní řádky jinak
 where
  sekni "" = ("","")                           - - prázdný řetězec
  sekni ('\n':zb) = ("",'\n':zb)               - - konec řádku
  sekni (x:zb) = let (l, zb') = sekni zb in (x:l,zb')
                             - - jinak odtrhni první písmeno (x), sekni
                             - - zbytek (zb) na l a zb' a před l připoj x
 
mensi::Int->Int->Int               - - vrátí menší ze dvou čísel
mensi x y = if x < y then x else y

Řešení