První série třicátého čtvrtého ročníku KSP

Dostává se k vám první číslo hlavní kategorie 34. 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. Také na kuchařky na 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 budou 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 (této 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 úloha34-1-1 Běžkař (10 bodů)


Kevin si na jaře vyrazil na Šumavu na běžky. Jenže na některých místech už je sníh téměř roztátý, takže se na běžkách místy pohybuje velice obtížně. Časté sundavání a nandavání běžek je ale časově náročné a Kevin by se potřeboval na hotel dostat co nejrychleji.

Mapu Šumavy si můžeme představit jako neorientovaný graf (pokud nevíte, jak takový graf vypadá, doporučujeme si přečíst kuchařku). Mezi křižovatkami vedou cesty, které mají ohodnocení: kolik minut Kevinovi zabere projet cestu na běžkách a za jak dlouho ji projde se sundanými běžkami. Sundávat a nasazovat běžky Kevin může pouze na křižovatce a zabere mu to K minut. Na začátku má Kevin běžky nasazené, na konci cesty je musí mít sundané.

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 dostanete počet křižovatek N, počet cest M, na kolikáté křižovatce se Kevin nachází, na kolikátou křižovatku se chce dostat a čas sundavání a nandavání běžek K. Na každém z následujících M řádků budou 4 čísla: Ai, Bi, Xi a Yi.

Hodnoty Ai a Bi určují, mezi kterými dvěma křižovatkami vede i-tá cesta. Xi určuje, jak dlouho Kevinovi potrvá cestu přejet na běžkách, a Yi určuje, jak dlouho ji potrvá přejít pěšky.

Všechny vrcholy jsou očíslovány od 0 do N - 1 včetně.

Formát výstupu: Na výstup vypište jediné číslo – nejkratší čas, za který je Kevin schopen se dostat do cíle.

Ukázkový vstup:
3 3 0 2 3
0 1 2 3
1 2 5 4
2 0 50 50
Ukázkový výstup:
9

Teoretická úloha34-1-2 Líný student (11 bodů)


Se začátkem semestru si začal Vašek zapisovat přednášky. Jenže se bojí, aby si předmětů nezapsal příliš, a měl vůbec čas i na přípravu KSP. Ovšem rád by zabránil tomu, aby za ním mohl přijít nějaký jeho kamarád a říct mu, ať si zapíše ještě nějakou další přednášku.

Každá přednáška je popsána časem začátku a konce. Všechny časy začátků a konců přednášek jsou navzájem různé.

Vašek si tedy chce vybrat přednášky tak, aby jich byl co nejmenší počet. Ovšem ještě chce, aby nemohl v době volného času stihnout navštěvovat ještě nějakou jinou přednášku od začátku do konce. Vymyslete algoritmus, který tyto přednášky za Vaška vybere.


Praktická opendata úloha34-1-3 Pilný student (12 bodů)


Filip nastoupil na vysokou školu a nestačil se divit. Tolik úkolů, to na střední nebývalo! A jak jsou dlouhé!

Každý z N úkolů má určitý počet bodů B za své splnění, a navíc má deadline, tedy datum, do kterého Filip úkol musí vypracovat. Deadline každého úkolu je specifikován jediným číslem D, totiž počtem dní (od teď), do kdy úkol musí být splněn (tedy například pokud D = 1, tak musí Filip splnit úkol buď dneska, nebo zítra). Pokud do tohoto data Filip úkol neudělá, tak úkol propadá a už za něj nemůže získat žádné body.

Filip ví, že za jeden den stihne splnit nejvýše jeden úkol. Nyní si chce rozvrhnout čas tak, aby maximalizoval počet získaných bodů. Pomozte mu s tím.

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 dostanete číslo N: počet úkolů, které Filip má zadané. Na každém z následujících N řádků bude popsán jeden úkol dvěma mezerou oddělenými čísly B a D, tedy počtem bodů za daný úkol a deadline daného úkolu.

Formát výstupu: Na první řádek vypište jediné číslo: maximální počet bodů, které Filip může získat, pokud si rozvrhne čas dobře. Na následujících N řádcích pak vypište jedno z možných optimálních řešení. Pro každý úkol vypište jeden řádek obsahující den, ve který Filip má daný úkol řešit, nebo případně -1, když ho řešit nemá.

Ukázkový vstup:
5
9 1
3 0
8 2
7 1
2 2
Ukázkový výstup:
24
0
-1
2
1
-1

Teoretická úloha34-1-4 Sjezdař (12 bodů)


Na svahu tvořeném nakloněnou rovinou je umístěno N závodních branek. Po tomto svahu jede sjezdař z kopce dolů po trase určené lomenou čárou, která musí projít všemi brankami. Branka je horizontální úsečka zadaná třemi čísly: jedna souřadnice Y a dvě souřadnice X určující pozici krajních bodů. Trasa sjezdaře musí protnout tuto úsečku (může také procházet jedním z krajních bodů). Pokud jsou souřadnice obou krajních bodů stejné, musí sjezdař projet přesně tímto bodem. Osa X směřuje horizontálně, osa Y směřuje dolů ze svahu.

Vaším úkolem je vymyslet algoritmus, který najde trasu s největší možnou strmostí. Strmost trasy nadefinujeme jako minimum ze strmostí jednotlivých úseků. Strmost úseku lomené čáry z bodu (x1, y1) do bodu (x2, y2) pak je (y2 - y1)/|x2 - x1|. Pokud x1 = x2 a y2 > y1, strmost vyjde nekonečná. (Případ, že y2 < y1, nemůže nastat – znamenalo by to, že sjezdař jede do kopce.)

Uvažujme následující příklad rozložení branek (každá branka je popsaná pomocí tří čísel – dvou x-ových souřadnic a jedné y-ové):

5 7 0
2 6 2
1 3 3
4 5 5
Optimální trasa má strmost 3/2 a vypadá takto:
Příklad

Teoretická úloha34-1-X1 Rostoucí strom (teoretická) (8 bodů)


Kristýna se nedávno rozhodla k uctění hroších bohů založit arboretum. Zde hodlá pěstovat vzácný druh stromů – hrošeň.

Zatím má pouze jediné semínko představující první vrchol stromu – kořen. Strom bude postupně růst a Kristýnu vždy bude zajímat vzdálenost nějakého vrcholu od kořene (aby měla přehled, které vrcholy jsou dostatečně vysoko, takže hroší bohové na ně určitě uvidí). Hrany stromu budou mít různé délky a vzdáleností myslíme součet délek na cestě mezi daným vrcholem a kořenem.

Úkolem je zpracovávat následující operace:

Na operace je potřeba odpovídat online. To znamená, že po načtení dotazu třetího typu je třeba vypsat výsledek předtím, než načtete další řádek vstupu.


Praktická opendata úloha34-1-X2 Rostoucí strom (praktická) (8 bodů)


Jelikož je uctívání hroších bohů ryze praktická záležitost, nyní si předchozí úlohu naimplementujeme!

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.

Vrcholy číslujeme postupně od nuly. Kořen má tedy číslo nula. První typ operace přidá vždy vrchol s nejmenším zatím nepoužitým číslem.

Vstupem je binární soubor. Skládá se z čísel, každé je uložené v pořadí od nejméně významného bytu k nejvýznamnějšímu (tzv. little-endian formát).

Vstup začíná čtyřbytovým číslem Q, které značí počet operací. Následuje Q bloků po čtyřech bytech, každý reprezentuje jednu operaci. Každý z nich se skládá z jednoho trojbytového čísla A a jednoho jednobytového čísla B. Nechť O je odpověď na předchozí dotaz na vzdálenost (pokud ještě žádná nebyla, tak 0) a N je aktuální počet vrcholů. Označme X = (A + O) mod 3N. Podle hodnoty X daný blok reprezentuje určitou operaci:

Výstupem je textový soubor obsahující jediné číslo – odpověď na poslední otázku na vzdálenost.