Druhá série začátečnické kategorie třicátého šestého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Právě se díváte na leták druhé série 36. ročníku KSP-Z, neboli Korespondenčního Semináře z Programování, Začátečnické kategorie. Zapojit se může každý středoškolák i základoškolák.
Letos bude v KSP-Z pět sérií po čtyřech úlohách za celkem 220 bodů. Pokud budete mít jakoukoliv otázku, neváhejte se zeptat. Kontaktní adresy najdete v patičce na konci letáku. Přejeme hodně štěstí!
- Termín série: neděle 10. prosince ve 32:00 (tedy další ráno v 8:00), praktické úlohy za třetinu bodů až do 17. prosince
- Odevzdávání: elektronicky přes Odevzdávátko
- Jak řešit: viz Návod na teoretické úlohy a Návod na praktické úlohy
- Dotazy ohledně zadání: posílejte na ksp@mff.cuni.cz, nebo se ptejte na Discordu KSP.
Zadání úloh
36-Z2-1 Kevin a krtiny (8 bodů)
Kevin si chce na své zahrádce vypěstovat čaj. Jenže se mu tam usadili krtci, kteří mu tam dělají krtiny, ve kterých přece nemůže pěstovat ušlechtilý čaj. Nezbývá mu nic jiného, než krtiny zahladit. Našel v garáži motyčku, kterou použije. Zahlazováni krtin je ale náročná práce, Kevin by tedy chtěl motyčku použít co nejméně-krát.
Kevinova zahrádka je jedna dlouhá řada políček, na kterých se může a nemusí nacházet krtina. Motyčka je dlouhá M a na jedno použití odstraní všechny krtiny na M políčkách vedle sebe. Krtiny ale nemusí být vedle sebe, dokud je jejich vzdálenost menší než M, je možné je zahrabat jedním hrábnutí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 dvě kladná celá čísla: M – délku motyčky a N – počet krtin na zahrádce. Na dalším řádku dostanete N pozic krtin oddělených mezerami. Pozice budou seřazeny vzestupně od začátku zahrádky. Políčka zahrádky indexujeme od 1.
Formát výstupu: Na výstup vypište jediné číslo – nejmenší počet použití motyčky, kterým lze zahladit všechny krtiny.
3 4 2 7 8 12
3
Máme motyčku šířky 3. První krtina je daleko od ostatních, musíme ji zahrabat samostatně. Další dvě jsou u sebe na pozicích 7 a 8, tím pádem je dokážeme zahladit najednou. Na poslední ale nedosáhneme, takže celkový nejmenší počet použití motyčky je 3.
36-Z2-2 Oběd v továrně (12 bodů)
Kevin jel na třídní exkurzi do továrny na raketové součástky. Při polední přestávce mu ale spadla svačinová krabička z lešení na běžící transportní pás o patro níž. Ztráta krabičky je nepřijatelná, protože Kevin má velký hlad. Naštěstí ale dostal od průvodce mapu pásů v továrně. Pomůžete mu najít, kde jeho oběd skončí?
Máme 2D mřížku R×S. Na každém políčku je pás. Každý pás posunuje předměty na sobě ve směru, kterým vede (nahoru, dolů, doprava, doleva). Kevinova krabička spadla na pozici x, y. Vypište 2 čísla – souřadnice, na kterých krabička vypadne z mřížky. Garantujeme, že cesta krabičky vždy končí na jednom z krajů mřížky.
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 4 kladná celá čísla: R, S, x,
y. R je počet řádků mřížky, S je počet sloupců mřížky, x a y jsou
souřadnice, kde Kevinovi spadl oběd (číslujeme od nuly). Na následujících R řádcích jsou S
dlouhé řádky mřížky skládající se ze znaků popisující jednotlivé pásy: v
(dolů), ^ (nahoru), > (doprava), < (doleva). Souřadnice
X roste doprava, Souřadnice Y roste dolů.
Formát výstupu: Vypište 2 celá čísla – poslední pás v mřížce, na kterém Kevinův oběd byl, než vypadl.
3 6 0 0 >v>v>v v<^>^v >>^v<<
3 2
36-Z2-3 Počítačová hra (14 bodů)
Kevin si na své oblíbené herní platformě Pára zdarma stáhl novou počítačovou hru. V této hře může Kevin nakupovat různé předměty a z těchto předmětů pak vyrábět předměty jiné. Cíl hry je prostý – pomodlit se hroším bohům, ale k tomu je potřeba získat bronzovou sošku hrošíka. A to buď jejím koupením, anebo vyrobením z jiných předmětů. Tyto předměty si opět buď může nakoupit, či vyrobit. A tak dále.
Má to ale jeden háček. Za kupování předmětů ve hře se musí platit reálnými penězi. Kevin si sice od tatínka půjčil kreditní kartu, i tak by ale chtěl utratit ve hře co nejméně. Proto se obrátil na vás s žádostí o pomoc. Pomůžete Kevinovi nalézt nejlevnější způsob, jak získat hroší sošku?
Nyní o něco formálněji. Máme N předmětů s čísly 0 až N-1, kde předmět s identifikačním číslem 0 je bronzová soška hrošíka, kterou se Kevin snaží získat. Každý z předmětů má svoji cenu Ci, za kterou jej lze koupit přímo. Dále ve hře existuje M receptů na výrobu nějakého z předmětů. Každý recept vyrábí nějaký předmět z několika jiných předmětů. Vždy platí, že předmět vyrábíme jen z předmětů s větším identifikačním číslem. Při výrobě se zničí všechny předměty, ze kterých se vyrábí, tedy je nelze použít opakovaně. Vaším cílem je určit nejnižší cenu, za kterou lze získat sošku hrošíka.
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 dvě kladná celá čísla oddělená mezerou: N – počet předmětů ve hře a M – počet receptů. Na druhém řádku dostanete N nezáporných celých čísel. i-té z nich určuje kupní cenu i-tého předmětu. Na dalších 2M řádcích dostanete informace o jednotlivých receptech – každý z nich zabírá dva řádky vstupu. Na prvním řádku pro daný recept dostanete dvě celá čísla – nezáporný identifikátor předmětu, který lze daným receptem vyrobit, a kladný počet ingrediencí X, ze kterých se daný předmět dá vyrobit. Na dalším řádku následuje X čísel, která určují předměty, ze kterých se vyrábí.
Formát výstupu: Na výstup vypište jediné číslo – nejnižší cenu, za kterou lze získat předmět s identifikátorem 0.
7 6 8 3 9 7 1 7 2 0 1 2 0 2 1 3 1 1 2 3 2 4 6 2 1 5 0 1 5
6
36-Z2-4 Stará trať (10 bodů)
Vilém dostal zprávu, že mu nedávno zesnulý prastrýc Archibald odkázal všechen svůj majetek. To ho velmi zaskočilo, obzvláště protože ani nevěděl, že nějakého prastrýce měl. Archibald totiž žil ve svém zámku za městem a už ho roky neopustil. Vilém se rozhodl, že nejlepší způsob, jak uctít prastrýcovu památku, je přestěhovat se do jeho domu a poznat, jak žil.
Do zámku vedla soukromá jednokolejná železnice, ale po rocích nepoužívání je dosti zchátralá. Po trati jsou rozmístěné zrychlováky a zpomalováky regulující rychlost vlaku. Některé z nich jsou ale rozbité, takže bylo třeba je odstranit. Proto teď hrozí, že se vlak zastaví uprostřed tratě, nebo naopak na konci nestihne zabrzdit. Vilém si nemůže dovolit nechat je opravit, takže místo toho musí některé ze zbývajících deaktivovat. To je hodně práce, takže jich chce deaktivovat co nejméně. Pomozte mu vybrat které.
Vlak na začátku vyjíždí rychlostí jedna. Pokaždé, když projede zrychlovákem, zrychlí o jedna. Pokaždé, když projede zpomalovákem, zpomalí o jedna. Pokud rychlost klesne na nulu, vlak zastaví a nedorazí do cíle. Pokud vlak dorazí do cíle s rychlostí větší než jedna, nestihne zabrzdit a vykolejí se. Na vstupu dostanete posloupnost zbývajících (funkčních) zrychlováků a zpomalováků. Vyberte z nich co nejméně k deaktivování tak, aby vlak dorazil v pořádku do cíle.
Například pro vstup - + + - + - + - (kde + je zrychlovák a - je zpomalovák)
by možné řešení bylo deaktivovat první zpomalovák a třetí zrychlovák.
Toto je teoretická úloha. Není nutné ji programovat, odevzdává se pouze slovní popis algoritmu. Více informací zde.
