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

Dostává se k vám čtvrté čí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


Teoretická úloha36-4-1 Oprava vzducholodi (10 bodů)


Kevin ve svém povánočním úklidu pokoje naprosto selhal a usoudil, že bude nejlepší se nadobro přestěhovat. Nájmy však nejsou v dnešní době zrovna nejlevnější, a tak se Kevin po uvážení různých alternativ rozhodl usídlit v oblacích.

Pořídil si za tímto účelem prastarou vzducholoď, která je aktuálně ve velmi špatném technickém stavu. Kevina tak čeká před prvním vzletem spousta práce – bude muset provést rozsáhlé opravy, sehnat dostatek paliva, podplatit místní úřady…

Aby se Kevin ve svých četných povinnostech vyznal, vytvořil seznam N úkolů a u každého z nich si poznamenal předpokládanou dobu potřebnou k jeho provedení. Platí, že některé úkoly nelze provést, dokud nebudou hotovy úkoly jiné, třeba před celkovou opravou bude určitě nutné pořídit náhradní díly a zakoupit správné nářadí. Zároveň některé úkoly nemusí záviset na ničem, například nákup občerstvení na kolaudační večírek či objednání nového nábytku.

Na úkoly lze nahlížet jako na vrcholy orientovaného grafu, kde z vrcholu u do vrcholu v vede hrana právě tehdy, když úkol u závisí na úkolu v. Vrcholy klidně mohou mít víc vstupních a výstupních hran, nicméně se nemůže stát, že by byl v grafu nějaký cyklus.

Můžete předpokládat, že má Kevin vždy k dispozici dostatek pomocné pracovní síly, takže je schopen provádět libovolné množství úkolů najednou.

Při takto rozsáhlém projektu se může snadno stát, že u nějakého úkolu dojde ke zpoždění a veškerá práce bude v důsledku toho dokončena později. Kevin by rád takové situaci předešel a zajímalo by ho, jakých úkolů se to týká.

Vaším úkolem bude pro Kevina vytvořit algoritmus, který obdrží na vstupu doby provedení jednotlivých úkolů, orientovaný acyklický graf jejich závislostí a nalezne všechny úkoly, pro které platí, že jakékoliv malé zpoždění nutně prodlouží nejkratší čas, za který je možné veškerou práci dokončit.

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


Praktická opendata úloha36-4-2 Megasněhulák (12 bodů)


Kevin se vracel s kamarády ze školy. Právě přecházeli další z mnoha lyžařských sjezdovek v Hroším Týnci, když narazili na haldu sněhových koulí. Už je ale přestaly bavit soutěže ve stavění sněhuláků, takže se rozhodli spojit síly a postavit jednoho obřího sněhuláka – megasněhuláka.

Rozhodli se, že ke stavbě megasněhuláka použijí právě K koulí. Těchto K koulí poskládají nad sebe. Aby se sněhulák nezhroutil, musí být každá koule ostře menší než ta pod ní. Speciálně tedy není možné použít dvě koule stejné velikosti.

Kevinovi kamarádi rychle změřili velikost každé z N koulí. Každá koule vypadá trochu jinak, a vzhled sněhuláka závisí na každé z použitých koulí. Než se Kevinovi kamarádi rozhodnou, jaké koule použijí, rádi by věděli, kolika způsoby mohou megasněhuláka postavit. Pomůžete jim?

Počet možných megasněhuláků může být opravdu velký, takže stačí, když vypočítáte jeho zbytek po dělení číslem 1 000 000 007.

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 budou čísla N a K – počet koulí, které mají Kevinovi kamarádi k dispozici, a počet koulí, které chtějí použít. Na dalším řádku bude N čísel představující celočíselné velikosti dostupných koulí.

Formát výstupu: Na výstup vypište jedno číslo, a to zbytek po dělení počtu možných sněhuláků číslem 1 000 000 007.

Ukázkový vstup:
5 3
1 2 5 3 3
Ukázkový výstup:
7

Vysvětlení ukázkového vstupu: Označme koule po řadě 1, 2, 5, 3a a 3b. Kevinovi kamarádi celkem mají sedm různých možností, jak z nich megasněhuláka postavit:


Teoretická úloha36-4-3 Sklad s bednami (13 bodů)


Kevin se nechal zaměstnat ve velkoskladu jisté firmy specializující se na prodej beden jako skladník. Pracuje v obrovském skladu C-21d, který je vyhrazen pro krychlové bedny velké jeden metr (pro jinak velké bedny má přeci firma jiné sklady).

Jednou v pondělí se ocitl ve skladu úplně sám a začal si hrát. Jezdil s vozíkem různě po skladu a občas, když se mu do cesty připletly nějaké bedny, tlačil je před vozíkem. Když se vydováděl, shledal, že způsobil pěkný chaos. Bedny jsou teď rozesety po skladu na obrovské ploše a nikdo neví kde přesně. Naštěstí si vzpomněl, že vozík si ukládá historii pohybů a ve firemní databázi je zapsáno, kde se nacházely bedny na začátku dne. Jistě tedy půjde dopočítat, kde jsou bedny teď. Pomůžete mu?

Sklad si, protože je opravdu obrovský, můžeme představit jako nekonečnou čtvercovou mřížku. Známe pozice beden předtím, než je Kevin začal posouvat. Dále známe počáteční pozici vozíku a posloupnost jeho pohybů (ve směrech nahoru, dolů, doprava, doleva). Když jede vozík nějakým směrem, tlačí před sebou všechny bedny v daném směru až po tu, před kterou je volné políčko. Na konci nás zajímají všechny pozice, na kterých skončí nějaká z beden (je jedno, která kde, bedny jsou vzájemně nerozlišitelné).

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


Praktická opendata úloha36-4-4 Heslo (10 bodů)


Experimentální úloha

Kevin si stáhl novou aplikaci ministerstva pro byrokracii, kam potřebuje nahrát svoje dokumenty.

Bohužel se ale ukázalo, že vytvořit si účet je trošku složitější…

Ukázkový vstup:
Zadej heslo dle vyhlášky č. 42:
Ukázkový výstup:
slavahrosimbohum

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.

Na odevzdávání úlohy doporučujeme použít ksp-klienta nebo naše API.


Teoretická úloha36-4-X1 Počet koček (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.

„Jů, tady jsou kočky!“ zavýskl Pepíček nad knížkou. Maminka žádnou kočku neviděla, tak jí musel Pepíček jednu předvést. Prvním chapadlem ukázal na K, druhým na O v následujícím odstavci, třetím na Č o kus dál, čtvrtým na další K a pátým na A v posledním řádku. Pak zvesela pokračoval: „Už jsem jich na téhle stránce našel přes 200. Kolik jich asi bude v celé kapitole? V celé knížce?“

Pepíček o tom sice ještě neví, ale hodila by se mu datová struktura. Vytvořili bychom ji pro nějaký řetězec k délky K (kočku) a řetězec t délky T (text knížky). Datová struktura by pak uměla pro libovolný (souvislý) podřetězec t[i],… ,t[j] říci, kolikrát se v něm vyskytuje kočka – tedy kolika způsoby lze vybrat indexy a1,… ,ak tak, aby platilo i≤ a0 < a1 < … < aK-1 ≤ j a t[a0] = k[0], …, t[aK-1] = k[K-1].

Navrhněte co nejefektivnější takovou strukturu. Předpokládejte, že struktuře chceme položit řádově T dotazů a že K je mnohem menší než T.

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