Třetí série třicátého šestého ročníku KSP

Dostává se k vám třetí číslo hlavní kategorie 36. ročníku KSP.

Letos se můžete těšit v každé z pěti sérií hlavní kategorie na 4 normální úlohy, z toho alespoň jednu praktickou opendatovou. Dále na kuchařky obsahující nějaká zajímavá informatická témata, hodící se k úlohám dané série. Občas se nám také objeví bonusová X-ková úloha, za kterou lze získat X-kové body. Kromě toho bude součástí sérií seriál, jehož díly mohou vycházet samostatně.

Autorská řešení úloh budeme vystavovat hned po skončení série. Pokud nás pak při opravování napadnou nějaké komentáře k řešením od vás, zveřejníme je dodatečně.

Odměny & na Matfyz bez přijímaček

Za úspěšné řešení KSP můžete být přijati na MFF UK bez přijímacích zkoušek. Úspěšným řešitelem se stává ten, kdo získá za celý ročník (hlavní kategorie) alespoň 50% bodů. Za letošní rok půjde získat maximálně 300 bodů, takže hranice pro úspěšné řešitele je 150. Maturanti pozor, pokud chcete prominutí využít letos, musíte to stihnout do konce čtvrté série, pátá už bude moc pozdě. Také každému řešiteli, který v tomto ročníku z každé série dostane alespoň 5 bodů, darujeme KSP propisku, blok, nálepku na notebook a možná i další překvapení.

Zadání úloh


Praktická opendata úloha36-3-1 Modla pro hroší bohy (11 bodů)


Obyvatelstvo Hrochova vždy žilo v míru a pokoji pod ochranou hroších bohů. Poslední dobou je ale začala sužovat častá zemětřesení. Jestli to takhle půjde dál, tak zanedlouho z města nic nezbude. Určitě museli své bohy něčím rozhněvat. Aby si je udobřili a zachránili město, rozhodli se vzít největší kámen, který vydolovali v místním lomu, a udělat z něj modlu pro hroší bohy. Aby minimalizovali šanci dalších zemětřesení, rozhodli se modlu postavit tak, aby byla co nejvyšší. Hroší bohové přece nebudou chtít třást zemí, když tím hrozí, že si povalí vlastní modlu.

Kámen má tvar konvexního mnohoúhelníku. Najděte, na kterou stranu se má postavit, aby byl nejvyšší. Modla bude podepřená, takže může stát na libovolné straně, bez ohledu na polohu těžiště. Pokud více stran dosáhne stejné výšky, můžete vybrat libovolnou.

Toto je praktická open-data úloha. V odevzdávátku si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

Formát vstupu: Na prvním řádku je číslo N – počet vrcholů mnohoúhelníku. Na každém z dalších N řádků jsou celočíselné souřadnice x a y jednotlivých vrcholů.

Formát výstupu: Na výstup vypište jedno číslo – index strany, na kterou se má mnohoúhelník postavit. Strany jsou indexované podle prvního vrcholu. Strana jedna vede mezi prvním a druhým, strana dva mezi druhým a třetím a tak dále, až nakonec hrana N vede mezi N-tým a prvním.

Ukázkový vstup:
5
-1 2
-1 -1
2 -1
5 3
3 5
Ukázkový výstup:
4
Kámen

Na první a druhé straně má výšku 6, na třetí a páté 4,2 a na čtvrté 5√2. Nejvyšší je tedy na čtvrté.

Řešení


Teoretická úloha36-3-2 Paměťově omezený tablet (11 bodů)


„Tablete, tablete, řekni mi, kdo je na světě nejsymetričtější?“ ptá se opět král. Tentokrát se ovšem neptá kouzelného zrcadla. Zrcadlo král vyhodil a pořídil si chytrý nástěnný tablet! Tablet vyfotí kamerami spoustu obrázků krále a vyhodnotí jeho symetričnost na svém procesoru. Nicméně výrobci šetřili, dali mu málo paměti, která sotva stačí na pár obrázků.

Tentokrát není problém v rozhodování symetričnosti krále, to tablet hravě zvládne. Ale aby to udělal, musí nejdříve pořízené obrázky předzpracovat – vlastně vyhodnotí něco jako matematický výraz, který s obrázky počítá: nejdříve „zprůměruje“ obrázek levého ucha krále s jeho nosem, poté „sečte“ obrázky levé a pravé nohy, výsledky spolu „vynásobí“, a tak dále…Výpočet na obrázcích se vlastně dá popsat binárním stromem.

Vstupem vašeho algoritmu bude binární strom, který popisuje vyhodnocování nějakého „matematického“ výrazu, který ale místo s čísly počítá s obrázky. Listy jsou obrázky krále, vnitřní vrcholy reprezentují operaci, která nějak kombinuje dva obrázky do jednoho či transformuje jediný obrázek (vrcholy s jen jedním synem jsou tedy povoleny, viz příklad níže), výsledek z kořene je pak finální obrázek, ze kterého tablet už snadno určí symetrii krále. Obrázky jsou ale velké, tudíž vaším úkolem je vymyslet, jak zadaný strom vyhodnotit v takovém pořadí, abyste si v průběhu museli pamatovat co nejméně obrázků. Máte tedy najít jakýsi plán výpočtu.

Všechny obrázky, tedy listy i výsledky vnitřních vrcholů, jsou stejně velké. Obrázky v listech jsou v počátku výpočtu uloženy na disku tabletu, paměť tedy spotřebují, až jakmile je chcete použít pro vyhodnocení nějaké operace. Pro vyhodnocení typického vnitřního vrcholu se dvěma potomky je vždy potřeba použít minimálně tři kusy paměti zároveň: dva, ve kterých už jsou uloženy obrázky obou potomků vyhodnocovaného vrcholu (ať už jsou vnitřním vrcholem nebo listem), a jeden, kam se uloží výsledek.

Struktura stromu je dána pevně a není možné ji měnit. Například nelze využívat případné komutativity nebo asociativity operací ve vrcholech – o operacích ostatně vůbec nic nevíme.

Vymyslete algoritmus, jak pro libovolný binární strom určit pořadí vyhodnocování vrcholů, při kterém se spotřebuje přesně optimální množství paměti. Pozor, že nám nestačí asymptoticky optimální paměť, chceme jí opravdu spotřebovat co nejméně v absolutních číslech: plán, který na nějaký strom spotřebuje paměť na 10 obrázků, je horší než plán, který musí ukládat jen 9 obrázků. Tedy počet zapamatovaných obrázků v paměťově nejnáročnějším místě vámi naplánovaného výpočtu musí být co nejnižší. Paměť měříme pouze na počet obrázků.

Naopak váš algoritmus, který bude plán hledat, nemá žádná časová nebo paměťová omezení. Jeho časová složitost by ale měla být, tentokrát asymptoticky, co nejrychlejší.

Ilustrace stromu výpočtu

V příkladu výše by plán výpočtu, který počítá vnitřní vrcholy (či načítá listy) v pořadí 3, 1, 4, 5, 2, 0, použil v nejnáročnějším místě výpočtu paměť na 4 obrázky, a to při počítání vrcholu číslo 2, protože je potřeba si pamatovat výsledek z vrcholu 3, listy 4 a 5 a navíc i místo na výsledek pro vrchol 2.

Plán 4, 5, 2, 3, 1, 0 je ovšem lepší, a v tomto případě i optimální. V nejnáročnějším místě si totiž pamatuje jen 3 obrázky. Toto nastane hned několikrát, konkrétně při počítání vrcholů 2, 1 a také 0.

Toto je teoretická úloha. Není nutné ji programovat, odevzdává se pouze slovní popis algoritmu. Více informací zde.

Řešení


Teoretická úloha36-3-3 Hromady odpadu (12 bodů)


Vánoce a Silvestr skončily a zanechaly za sebou spoustu nepořádku. Kevin se proto rozhodl, že by si rád letos u sebe doma pořádně uklidil. Nebude to však mít jednoduché, tuto činnost během minulého roku značně zanedbával a v pokoji mu mezitím vyrostlo N hromad odpadu. Každá taková hromada má nějakou výšku vi a odpovídá sloupci na sobě naházených vi předmětů.

Protože Kevin rád pracuje efektivně, přinesl si k usnadnění úklidu pracovní nářadí – lopatu a velmi silnou kyselinu.

Lopatou je schopen vždy nabrat libovolný počet předmětů z vrchu jedné z hromad a vyložit je kousek vedle. Tím danou hromadu sníží o nějaké celočíselné k a zároveň založí novou hromadu výšky k. Kevinův pokoj je neobvykle prostorný, takže takto může v průběhu úklidu založit libovolný počet hromad celočíselné výšky.

Pokud Kevin nechce odpad jen přemístit, ale přímo zničit, použije kyselinu. Tu je schopen jedním pohybem rovnoměrně rozprostřít po všech hromadách a nechat ji na každé hromadě rozleptat jeden předmět z vrchu.

Vaším úkolem bude vytvořit algoritmus, jež pro Kevina nalezne nejkratší možnou posloupnost těchto dvou operací, tedy rozdělení jedné hromady na dvě celé části a snížení všech hromad o 1, vedoucí k odstranění veškeré nečistoty.

Můžete předpokládat, že jsou hromady poměrně nízké. Tím myslíme, že výška nejvyšší z hromad bude řádově tak velká jako celkový počet hromad N.

Pokud má například Kevin v pokoji hromady výšek 5, 7, 13, tak je jeden z možných postupů použít kyselinu a snížit všechny hromady o 1. Tím získáme hromady výšek 4, 6, 12. Následně v jednom kroku rozdělíme hromadu výšky 12 na dvě hromady výšky 6. Zbyly nám tak hromady výšek 4, 6, 6, 6, kterých se jednoduše zbavíme použitím kyseliny šestkrát za sebou. K úklidu jsme celkem potřebovali 8 kroků a lze ukázat, že rychleji to nejde.

Toto je teoretická úloha. Není nutné ji programovat, odevzdává se pouze slovní popis algoritmu. Více informací zde.

Řešení


Praktická opendata úloha36-3-4 Nejlepší programovací jazyk, část III. (11 bodů)


Experimentální úloha

V předchozí části jsme se naučili vyrábět konstanty a duplikovat čísla. Tentokrát je čas v ksplangu – našem nejlepším programovacím jazyku – konečně napsat nějaké pořádnější programy.

Pokud jste ne(vy)řešili předchozí část, vůbec to nevadí. Nahlédněte do řešení předchozí části, kde najdete potřebné stavební bloky (vyrobení nuly, záporných čísel, univerzální duplikaci), které můžete v této části vkládat do svých programů.

Do řešení předchozí části se podívejte i v případě, že jste předchozí úlohu vyřešili. Naleznete v něm totiž duplikaci, která je univerzální, tedy zvládne zduplikovat libovolné číslo. V předchozí úloze stačilo naprogramovat duplikaci pro omezený rozsah čísel, nicméně tentokrát se bude na řešení úkolů hodit právě tato univerzální varianta. Také je možné, že v řešení najdete nové užitečné triky.

Kromě toho jsme vylepšili náš simulátor, nyní je v něm možno program krokovat a podívat se na stav zásobníku po každé instrukci. Další novinkou je možnost zapnout textový režim, kdy do zásobníku můžete zapisovat text. Vstupní text se převede na Unicode code pointy a výstup programu se po doběhnutí také vypíše jako text. V této úloze textu ještě nevyužijeme, ale zlepšuje to možnost použití ksplangu v produkci.

Tuto úlohu odevzdávejte v odevzdávátku, podobně jako běžné opendata úlohy. Generované vstupy můžete v odevzdávátku ignorovat, vaše ksplangové programy odevzdávejte v textové podobě jakožto výstup k danému úkolu. Po odevzdání je náš interpreter ksplangu spustí na několika neveřejných testovacích vstupech a dá vám vědět o výsledku.

Zásobník má omezený počet prvků, v této úloze vždy 2 097 152, a jeho překročení ukončí program chybou. Ve všech úkolech můžete předpokládat, že se na zásobník vejde aspoň dalších 1000 čísel. Narozdíl od předchozí úlohy můžete při velmi neefektivní implementaci narazit na časový limit. Nastavili jsme jej tak, že by vaše programy měly stíhat doběhnout, i když jsou patnáctkrát pomalejší než naše referenční řešení.

Úkol 1 – Sekvence [3b]

Začneme rozcvičkou. Na vrcholu zásobníku je kladné číslo k. Nahraďte jej sekvencí k0, včetně.

Před číslem k mohou i nemusí být další hodnoty. Musí zůstat nezměněny. Na zásobník se vždy vejde aspoň 1000 + k dalších čísel.

Ukázkový vstup:
42 42 3
Ukázkový výstup:
42 42 3 2 1 0

Úkol 2 – Řazení [4b]

Na vrcholu zásobníku naleznete číslo k (k ≥ 1), a pod ním dalších k čísel. Na zásobníku nic jiného není. Seřaďte celý zásobník s výjimkou horního čísla k (počtu prvků) od nejmenšího na dně po největší navrchu. Počet prvků k na vrcholu zásobníku odstraňte, nezatřizujte jej.

Čísla k seřazení na zásobníku mohou být libovolná, zejména upozorňujeme, že by program měl umět zpracovat i číslo -263. Univerzální duplikaci, která zduplikuje libovolná čísla, naleznete v řešení předchozí části.

Ukázkový vstup:
3 4 -4 1 1 5
Ukázkový výstup:
-4 1 1 3 4

Úkol 3 – Počet čísel na zásobníku [4b]

V předchozím úkolu jsme dostali počet čísel na zásobníku šikovně připravený. To je ale pěkný podvod, při normálním použití nám toto nikdo nedá. Je čas to vyřešit.

Přidejte na zásobník jedno číslo: počet čísel při začátku běhu programu. Zásobník před tímto číslem musí zůstat zachován. Zásobník na vstupu není prázdný, vždy je na něm alespoň jedno číslo.

Čísla na zásobníku mohou být libovolná v celém rozsahu znaménkových 64-bitových čísel. Univerzální duplikaci, která zduplikuje libovolná čísla, naleznete v řešení předchozí části.

Ukázkový vstup:
1 356 -2
Ukázkový výstup:
1 356 -2 3

Řešení


Teoretická úloha36-3-X1 Výlet do Japonska (10 bodů)


Toto je bonusová úloha pro zkušenější řešitele, těžší než ostatní úlohy v této sérii. Nezískáte za ni klasické body, nýbrž dobrý pocit, že jste zdolali něco výjimečného. Kromě toho za správné řešení dostanete speciální odměnu a body se vám započítají do samostatných výsledků KSP-X.

Kevin je na školním výletu do Japonska. A protože let do Japonska je jaksi…dlouhý, rozhodl se, že se během něj naučí pár slovíček. Na letišti si koupil slovník a teď si v něm listuje.

Kevin se učí slova následujícím způsobem: Opakovaně se učí slabiky (posloupnosti znaků), na které narazí ve slovníku. Slovo potom umí vyslovit, když ho umí rozdělit na slabiky, které umí vyslovit. (Tyto slabiky se ale nesmí překrývat.)

Kevina by zajímalo po každé naučené slabice, kolik slov již umí vyslovit. Prozradíte mu to?

Počítejte s tím, že 1 ≪ |Smax| ≪ N ≪ Q. Každá hodnota je řádově větší než předchozí: Malá konstanta, délka nejdelšího slova, počet slov, počet naučených slabik.

Ukázkový vstup:
Slova:
konnichiwa
sumimasen
ichi
sushi
shinkansen

Naučené slabiky:
shi
su
nkan
s
en
ic
umimase
Ukázkový výstup:
0
1
1
1
2
2
2

Nejdřív Kevin bude umět vyslovit |su|shi| po dvou naučených slabikách. Po pěti naučených slabikách bude umět i |shi|nkan|s|en|.

Toto je teoretická úloha. Není nutné ji programovat, odevzdává se pouze slovní popis algoritmu. Více informací zde.

Řešení