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

Zadání úloh

13-5-1 Bláznivé hodiny (11 bodů)

Pan Johnson byl vynálezce. Ačkoliv někteří lidé o jeho genialitě pochybují, nelze mu upřít několik velmi zajímavých vynálezů. Patří mezi ně i jedny velmi speciální hodiny. Tyto hodiny vypadají přibližně jako svislá trubice s kovovými koulemi seřazenými za sebou. Koule jsou očíslované čísly od tří do N a na počátku jsou podle těchto čísel vzestupně seřazeny. Hodiny pracují tak, že v jednom tiku vezmou kouli ze spodu trubice a přesunou ji o tolik míst výše, kolik je její číslo (důmyslný mechanismus v průběhu přesunu přidržuje koule nad místem vložení). Pokud je koule přemístěna dále za poslední kouli, automaticky propadne na místo těsně za poslední koulí. Jistě chápete, že přes bezespornou zajímavost tyto hodiny vykazují i jistou míru nepraktičnosti. Vlastník těchto hodin by tedy po vás chtěl, abyste mu napsali program, který dostane počet koulí v trubici a spočte, po kolika ticích se poslední koule dostane na první místo.

Příklad: Pro N=8 se poslední koule dostane na počátek po 7 krocích: 345678, 456378, 563748, 637485, 374856, 748356, 483567, 835647.

Řešení

13-5-2 Holiči (12 bodů)

V jednom trpasličím městě svou živnost provozovali dva holiči. Protože již zítra bude svátek Blyštivého briliantu, rozhodlo se mnoho trpaslíků (a proslýchá se, že i trpaslic), že si nechají upravit svůj vous. Problém ale je, že trpaslíci jsou dosti hašteřiví, a tak by se někteří u holiče mezi sebou pohádali. Tomu je třeba zabránit vhodným rozdělením trpaslíků mezi holiče. Zároveň je ale žádoucí, aby byli všichni zákazníci obslouženi co nejdříve.

Vaším úkolem je napsat program, který dostane na vstupu počet trpaslíků N a pak seznam dvojic trpaslíků, kteří se nesnáší. Na výstup by pak měl program vypsat pro každého trpaslíka, ke kterému holiči by měl jít, tak, aby žádná nesnášející se dvojice nešla ke stejnému holiči (pokud takové rozdělení trpaslíků neexistuje, stačí vypsat odpovídající zprávu). Navíc by měl být rozdíl mezi počty trpaslíků u jednotlivých holičů minimální.

Příklad 1: Oholit se chtějí 3 trpaslící. Nesnáší se 1–2, 2–3 a 1–3. V tomto případě rozdělení mezi holiče neexistuje.

Příklad 2: Oholit se chce 6 trpaslíků. Nesnáší se 1–2, 1–3, 2–4, 4–5. K prvnímu holiči mají jít trpaslíci 1, 4 a 6, k druhému 2, 3 a 5.

Řešení

13-5-3 Optimální strom (10 bodů)

Jsou dány délky d1, d2, … , dn setříděných posloupností v neklesajícím pořadí. To znamená d1≤ d2≤ … ≤ dn. Na slití dvou posloupností délek x a y je potřeba x+y porovnání. Navrhněte algoritmus a napište program, který určí minimální počet porovnání nutný ke slití všech posloupností. Nezapomeňte na důkaz správnosti vašeho algoritmu.

Příklad: Posloupnosti mají délky 2, 3, 5, 6 a 8. Slévání s nejmenším počtem porovnání slije nejdříve první a druhou posloupnost (5 porovnání), výsledek pak se třetí posloupností (10 porovnání). Potom slije čtvrtou a pátou posloupnost (14 porovnání) a nakonec výsledky předchozích dvou slévání (24 porovnání). Celkem bylo třeba 53 porovnání.

Řešení

13-5-4 Generátor (9 bodů)

Poté co jste po pana Broučka sestrojili vytoužený Konvertor, jeho vesmírné lodi už mnoho nechybí. Podpalubí má vybavené celé a na palubě chybí již jen opravit pár prkýnek, která poškodili dělníci při instalaci tachyonového děla. Pan Brouček ovšem přišel na závažný problém. Při konstrukci své lodi úplně zapomněl Generátor nepravděpodobnosti, který zajišťuje lodi ochranu proti meteoroidům a podobnému vesmírnému smetí. Generátor vypadá jako poměrně jednoduché zařízení – na zadané přirozené číslo odpoví nějakým jiným přirozeným číslem (na stejné přirozené číslo odpoví vždy stejně). Generátor má ovšem tu pozoruhodnou vlastnost, že posloupnost přirozených čísel A1, A2, A3,… , kde A1=1 a Ai pro i>1 je odpovědí generátoru na číslo Ai-1, se nikdy nezačne opakovat (tzn. každé číslo je v ní nejvýše jednou). Panu Broučkovi se nakonec podařilo jeden generátor sehnat v bazaru. Potřeboval by ale vyzkoušet, jestli notně opotřebovaný přístroj ještě funguje. A to už je úkol pro vás.

Napište program, který dostane na vstupu N a ověří, jestli se v prvních N prvcích generované posloupnosti vyskytne každé číslo nejvýše jednou. Váš program se může pouze dotazovat generátoru (v našem případě simulovaném uživatelem) na číslo následující po daném čísle. Dejte si v řešení pozor na to, že N může být značně velké a prvních N čísel posloupnosti se vám tedy zdaleka nemusí vejít to paměti.

Řešení

13-5-5 LISP (11 bodů)

Naše lispovská série pomalu končí a mnozí z vás si určitě již dávno řekli: „co to je za divný jazyk, ten lisp, vždyť to nemá ani objekty!“ a v duchu si přáli, abychom je před takovým preglaciálním monstrem uchrániti ráčili. Ale omyl – naše pochoutková úloha na závěr totiž ukáže, že objekty lisp ani mít nepotřebuje, neboť se v něm dají snadno naprogramovat.

Objekt je struktura v paměti, která obsahuje jednak proměnné (ty se obvykle nazývají atributy objektu), jednak funkce s tímto objektem pracující (těm se říkává metody). Objekt bude v naší lispové implementaci vlastně speciální forma. Metoda m objektu o se pak bude snadno volat jako (o m argumenty...). Hodnota atributu a objektu o se zjistí výrazem (o a) a do atributu se přiřadí nová hodnota h výrazem (o a h). Na atributy se tedy můžeme dívat jako na metody s jedním nepovinným argumentem. Pokud argument není specifikován, metoda jen vrátí příslušnou hodnotu. Pokud je argument specifikován, metoda atribut na tuto hodnotu přenastaví a vrátí ji i jako výsledek.

Nové atributy a metody vytváříme voláním následujících systémových metod, které dostanou do vínku všechny vytvořené objekty: Každý objekt v naší implementaci má následující systémové metody:

Nyní už jen zbývá popsat, jak vznikají nové objekty. Za tímto účelem je zde funkce object s jedním nepovinným parametrem. Volání object bez parametrů vytvoří nový objekt obsahující pouze systémové metody. Volání object s objektem o jako parametrem vytvoří kopii objektu o a tu vrátí, čímž snadno implementujeme objektovou dědičnost. Vaším úkolem je navrhnout funkci object, která bude generovat objekty se všemi popsanými vlastnostmi.

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

Řešení