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

Zadání úloh

15-2-1 Zatížení (10 bodů)

Bylo, nebylo. Za devatero dveřmi, devatero stoly a devatero stohy papíru leželo mezi razítky království Byrostánie. A nebylo to jen tak ledajaké království, bylo to království úředníků. Všichni úředníci každé ráno přišli do práce, svědomitě celou pracovní dobu bouchali razítky, podepisovali, schvalovali a pak večer odešli domů.

Jednoho dne si začali úředníci stěžovat, že jejich platy jsou příliš nízké, neboť nejenže stráví celou pracovní dobu razítkováním a jinou bohulibou činností, ale ještě musí dlouho do práce dojíždět. Když začali horkokrevnější úředníci volat po všeúřednické stávce, spočítal si rychle vrchní úředník a král v jedné osobě, že je zle (brzy by totiž zemřel zavalen listinami, které by psal, protože by je nikdo neodebíral). Rozhodl se proto zkrátit pracovní dobu o čas potřebný na dojíždění. K tomuto státotvornému kroku by ovšem potřeboval vědět, jak dlouho jezdí takový průměrný úředník do práce.

Vaším úkolem tedy je, napsat program, který dostane na vstupu počet měst v Byrostánii N (města si očíslujeme od 1 do N), dále počet silnic M a pak popis jednotlivých silnic (každá silnice je popsána čísly dvou měst, mezi kterými vede, a časem, který je třeba k jejímu projetí). Dále dostane program počet úředníku K a K dvojic čísel měst, mezi kterými příslušný úředník musí jezdit (mezi dvěma městy může jezdit i více úředníků). Na výstup má váš program vypsat nejmenší možnou (bereme všechny možnosti, kudy mohou úřednící do práce jezdit) průměrnou dobu, jakou úředníci stráví cestou do práce.

Příklad: Pro 5 měst, 5 silnic (1, 2, 1) (z města 1 do města 2 vede silnice s dobou jízdy 1 hodina), (1, 3, 2), (2, 4, 4), (3, 4, 3), (4, 5, 3) a 3 úředníky jezdící mezi městy (1, 5), (4, 1) a (3, 2) je nejmenší možná průměrná doba jízdy 16/3.

Řešení

15-2-2 Závorky (8 bodů)

Váš úkol v této úloze je velice jednoduchý. Napište program, který ověří, zda řetězec na vstupu složený ze znaků ( a ) tvoří korektní uzávorkování. Korektní uzávorkování je posloupnost znaků ( a ), ve které jdou znaky ( spárovat se znaky ) do dvojic takovým způsobem, že znak ( předchází znak ). Navíc pokud se první znak dvojice A vyskytuje před prvním znakem dvojice B, tak se druhý znak dvojice A vyskytuje za druhým znakem dvojice B.

Příklady: Řetězce (()(())) a ()() tvoří správné uzávorkování. Řetězce (() a ())( správné uzávorkování netvoří.

Řešení

15-2-3 Defragmentace (10 bodů)

Poté, co jste v minulé sérii pomohli stěhovací firmě Popruh a spol. vás nyní oslovila firma CCD (Corporation for Continuous Data) zabývající se stěhováním dat. Tato firma se mimo jiné zabývá i defragmentací disků. Poslední studie, které si firma nechala zpracovat, ukázaly, že optimální rozložení N souborů délek B1,… ,BN je takové, že první soubor leží na blocích 1,… ,B1, druhý soubor na blocích B1+1,… , B1+B2 atd. Navíc bloky jednoho souboru jsou seřazené podle svého pořadí v souboru. Protože CCD nyní vyvíjí nový software pro defragmentaci, požádala vás, abyste jí s ním pomohli.

Vaším úkolem je napsat program, který dostane na vstupu velikost disku D, počet souborů na disku N a pak popis N souborů. Popis i-tého souboru se skládá z počtu bloků Bi, které soubor obsahuje, a dále ze seznamu čísel Bi bloků (i-tý prvek seznamu odpovídá i-tému bloku souboru). Na výstup váš program musí vypsat libovolnou nejkratší posloupnost přesunů bloků, která uvede disk do výše popsaného stavu (přesun bloku je operace, která zkopíruje blok A na blok B).

Poznámka 1: Pro jednoduchost můžete předpokládat, že na disku je alespoň jeden blok volný.

Poznámka 2: Zkuste se při programování této úlohy vyhnout poli velikosti D – počet bloků na disku může být hodně velký, ačkoliv skutečný počet obsazených bloků je velmi malý.

Příklad: Pro disk velikosti 16 bloků a 2 soubory velikostí 3 a 5 na blocích 3,8,2 a 1,4,7,16,15 je posloupnost přesouvacích třeba 4→5, 1→4, 3→1, 7→6, 15→8, 2→3, 16→7, 8→2.

Řešení

15-2-4 Žabky (11 bodů)

Velevážené dámy, velectění pánové! Vítejte na představení přeslavného cirkusu Žamberto. Uvidíte nevídané artistické kousky, uslyšíte neslýchané vtipy našich klaunů a jako hvězda dnešního večera vystoupí sám pricipál Žamberto se svou drezurou stáda žab.

A skutečně. Po artistech a klaunech vešel do manéže bodrý chlapík a za ním skákalo několik žab oblečených do dresů. Poté co se všichni uklonili, seřadily se žabky na značkách do řady podle čísel na svých dresech. Principál pak řekl: „Hop!“ a jedna z žabek přeskočila na volnou značku. Když takhle žabky chvíli skákaly, zjistili jste, že žabky jsou teď seřazeny v opačném pořadí. Úžasné!

Tak takhle nějak by mohlo vypadat představení slavného cirkusu. Jenže žabky pana Žamberta jsou častým vystupováním už unaveny a nechtějí skákat. Pan Žamberto se tedy rozhodl, že zkusí vymyslet, jak naučit žabky skákat tak, aby se naskákaly co nejméně. A protože principál je přeci jen pouze cirkusák, měli byste mu s tímto úkolem pomoci vy.

Žabky mají na zemi vyznačeno N+1 značek. Na počátku stojí žabky na značkách 1,… ,N a značka N+1 je prázdná. V každém kroku může na volnou značku přeskočit žabka z nějaké značky s volnou sousedící, nebo ze značky ob jedno. Vaším úkolem je napsat program, který dostane na vstupu N – počet žabek – a vypíše postup (k popisu jednoho skoku žabky stačí vypsat značku, ze které žabka skáče na volné místo), jak mají žabky skákat, aby na konci stáli v opačném pořadí, volná byla buď první nebo poslední značka a přitom bylo provedeno co nejméně skoků. Body se udělují i za zdůvodnění, proč vaším programem navržený způsob vyžaduje nejmenší počet skoků.

Příklad: 4 žabky můžou skákat třeba následovně:

S (1234 ), 3 (12  43), 1 (2143), 2 (2  143),
4 (241 3), 5 (2413 ), 3 (24  31), 1 (4231),
2 (4  231), 4 (432  1), 5 (4321 )

Řešení

15-2-5 Haskell (12 bodů)

Jedním z rysů funkcionálních jazyků, který umožňuje značnou úsporu práce, je možnost psát funkce obecně, tj. tak, aby byly schopné bez modifikace pracovat nad různými druhy dat. Tuto schopnost jsme si demonstrovali již v minulé sérii na příkladech – funkce delka zjišťuje délku libovolného seznamu, bez ohledu na typ jeho prvků, obrat ho zase dokáže obrátit.

Podívejme se nyní na tuto ideu podrobněji. Zkusme napsat funkci, která quicksortem setřídí seznam. Propagační verze programu vypadá takto:

qsort [] = []
qsort (h:t) = qsort [x | x <- t, x <= h] ++ h : qsort [x | x <- t, x > h]
Když se budu držet prostředků, které jsem si zadefinoval, bude program o něco delší: 
qsort::[a]->[a]
qsort [] = []                      - - třídit prázdný seznam jde snadno...
qsort (h:t) = s                    - - jinak zvol první prvek jako pivot,
 where
  (m,v) = split h t                - - rozděl seznam na prvky menší než pivot a větší než pivot,
  ms = qsort m                     - - obě části rekurzivně setřiď
  vs = qsort v
  s = ms ++ h : vs                 - - a spoj je v odpovídajícím pořadí
 
  split p [] = ([],[])             - - rozdělení prázdného seznamu
  split p (x:r) =
    let (rm,rv) = split p r        - - nejprve rozděl tělo seznamu
     in if p < x then (rm,x:rv)    - - a pak přidej hlavu kam patří
                 else (x:rm,rv)

Drobný háček je v tom, že to nebude fungovat. Problém je v tom, že této funkci mohu podstrčit jakýkoliv seznam – a na jeho prvcích nemusí být žádným rozumným způsobem zavedeno porovnávání! Toto lze řešit několika způsoby:

Takových standardních „slibů“ je definováno více (Eq pro typy, u kterých lze testovat na rovnost, Show pro typy, které lze zobrazit, Num pro číselné typy, Bounded pro typy s omezeným rozsahem, …). Po parametrech funkcí můžeme požadovat i více vlastností, například u následující funkce provádějící porovnání dvou funkcí s omezeným definičním oborem:

sameFunction::(Bounded a, Num a, Eq b) => (a->b) -> (a->b) -> Bool
sameFunction f1 f2 =
  sameFromTo minBound maxBound  -- dvě fce jsou stejné, když jsou stejné 
                                -- na celém definičním oboru
 where
  sameFromTo from to = 
    if f1 from /= f2 from                    -- pokud se hodnoty neshodují
     then False                              -- funkce nejsou stejné
     else if from == to                      -- pokud už jsme na konci intervalu
            then True                        -- pak stejné jsou
            else sameFromTo (from + 1) to    -- jinak ještě musí být stejné na zbytku def. oboru

Samozřejmě žádný konečný seznam slibů není dostačující – pokaždé by se našla další užitečná vlastnost. Proto existuje způsob, jak si nadefinovat vlastní; a dokonce ani tyto standardní vlastnosti nejsou nijak vyjímečné. Deklarace pro výše použité Ord vypadá takto:

data Ordering = LT | EQ | GT deriving (Eq)
 
class (Eq a) => Ord a where
  (>),(<),(<=),(>=) :: a->a->Bool
  compare :: a->a->Ordering
 
  p1 < p2 = compare p1 p2 == LT
  p1 > p2 = compare p1 p2 == GT
  p1 <= p2 = compare p1 p2 /= GT
  p1 >= p2 = compare p1 p2 /= LT

Tato deklarace říká: aby typ měl vlastnost Ord, musí mít vlastnost Eq a musí pro něj být definována funkce compare pro porovnávání; dále pro takový typ existují funkce <, >, <=, >= definované uvedeným způsobem. Klauzule deriving (Eq) u definice typu Ordering ukazuje, že standardní vlastnosti jsou přeci jen trochu zvláštní – je možné tímto způsobem říci, že tato vlastnost má být definována zřejmým (co to přesně znamená, viz specifikace) způsobem.

Zbývá ukázat, jak zajistit, že typ má danou vlastnost. K tomu je potřeba nadefinovat všechny potřebné funkce. Například

data D = D Int Int deriving (Eq)
 
instance Ord D where
  compare (D x1 y1) (D x2 y2) =
    if x1 == x2
      then compare y1 y2
      else compare x1 x2

Taková definice může samozřejmě příslušnou vlastnost definovat i pro parametrizovaný typ; například toto je definice vlastnosti Eq pro funkce:

instance (Bounded a, Num a, Eq b) => Eq (a->b) where
  f1 == f2 = sameFunction f1 f2

A nyní úložka: Výše popsaný mechanizmus nám zjevně umožňuje psát „přetížené“ funkce, tj. funkce, které jsou definovány rozdílně pro různé typy parametrů. Co je již méně zřejmé je, že nám to též umožňuje obejít nemožnost psát funkce s proměnným počtem parametrů (jaký by taková funkce měla typ?). Zkuste napsat funkci, která se bude chovat podobně jako Céčkovská funkce printf; bude se tedy dát napsat

(printf "Muzeme vypisovat retezce: %s, cisla: %d a zase retezce: %s" "ret1" (8::Int) "ret2")::String

a výsledkem je řetězec "Muzeme vypisovat retezce: ret1, cisla: 8 a zase retezce: ret2".

Poznámky a rady:

Řešení