Druhá série začátečnické kategorie třicátého osmého ročníku KSP
Celý leták v PDF.
Druhá série KSP-Z je tady! Byla spuštena registrace na SMRŠŤ. Jde o víkendovou přednáškovou akci, která proběhne 28. 11. – 30. 11. 2025. Kvůli omezené kapacitě se ale musíte přihlásit.
Pokud se někde při řešení série zaseknete, nebo narazíte na jakýkoliv problém, neváhejte nám napsat na e-mail zdrojaky@ksp.mff.cuni.cz. Odpovíme vám co nejdříve. Pokud byste měli potíže s načítáním vstupů pro naše úlohy, tak jsme připravili návod v naší encyklopedii, který vám s tím pomůže.
Právě se díváte na leták druhé série 38. 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.
V průběhu roku vydáme několik dalších sérií úloh podobných této. 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 30. listopadu ve 32:00 (tedy další ráno v 8:00), praktické úlohy za třetinu bodů až do 7. 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
38-Z2-1 Kontrola vagónů (8 bodů)
Kevin má rád Sáru a Sářin tatínek řídí metro. Nejraději by do konce života nedělal nic jiného, než řídil metro, ale nebaví ho po dojetí na konečnou kontrolovat, že v žádném z vozů nikdo nezůstal a do tunelu neutekl žádný pes.
Kevin se nabídl, že pomůže s prvním problémem – zařídí pro Sářina tatínka program, který zpracuje data z počítadel cestujících v každých dveřích a napíše, jestli v některém z vozů někdo zůstal.
Počítadla jsou jednoduchá a hlásí jen že někdo vystoupil či nastoupil a číslo dveří, ke kterým patří. Počítadla se navíc občas mohou rozbít a tvrdí, že ze dveří někdo vystoupil, i když to není pravda – v takovém případě Sářin tatínek potřebuje vědět ve kterých vozech se to stalo, aby mohl závadu nahlásit údržbě. Pomůžete Kevinovi zařídit program pro Sářina tatínka a tím získat Sářinu přízeň?
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 čísla N, V a D – počet hlášení od počítadel,
počet vozů metra a počet dveří v každém vozu (všechny vozy mají stejný počet dveří).
Na následujících N řádcích následuje písmeno V (ven) nebo D (dovnitř) –
zda dveřmi vystoupil nebo nastoupil jeden cestující a číslo dveří.
Dveře i vozy číslujeme od 1.
Formát výstupu: Na jeden řádek vypište mezerou oddělená a vzestupně seřazená čísla vozů, ve kterých někdo zůstal.
Pokud v žádném z vozů nikdo nezůstal, vypište slovo PRAZDNY.
Pokud se nějaké počítadlo rozbilo a tvrdilo, že někdo vystoupil z vagónu,
který byl prázdný, vypište pouze CHYBA a číslo vozu, kde k tomu poprvé (nejdříve v seznamu hlášení) došlo, nehledě na to, zda někdo v některém z vozů zůstal.
5 5 3 D 6 D 5 D 9 V 6 V 4
3
38-Z2-2 Dýně (10 bodů)
Kevin má moc rád vyřezávání dýní, a proto se rozhodl, že letos jich chce vyřezat opravdu hodně. Jenže dýně jsou drahé, a tak jediným levnějším způsobem (mimo krádeže) je si je vypěstovat. Do Halloweenu ale nezbývá mnoho dní, a tak Kevin hledal, jestli existují nějaké dýně, které rostou rapidně rychle. Dýně ze semínek, která sehnal, se na poli rychle množí.
Když vyroste jedna dýně, další den se na všech prázdných místech vedle ní objeví další dýně. Předpokládejme, že Kevinovo políčko je přímka, takže nové dýně mohou vyrůst jen nalevo a napravo od původní. Zároveň na jednom políčku může růst nejvýš jedna dýně, takže když na sebe narazí dýně ze dvou stran, už se dál nešíří. Pole je také nekonečně dlouhé, aby mohl dýňový potenciál využít naplno. Kevinovi posléze došlo, že by rád věděl, kolik dýní bude na jeho políčku za určitý počet dní. Pomozte mu napsat program, který toto spočítá.
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ích dvou řádcích dostanete čísla D a T – počet dýní a počet dní. Na následujících D řádcích jsou vypsány souřadnice dýní v den 0.
Poznámka k implementaci: Kevin má času dost a pro pěstitelství je zapálený, takže vstupní čísla i výsledek mohou být velmi velká. Speciálně slibujeme jen, že se vejdou do znaménkového 64 bitového čísla. Pokud programujete v Pythonu, nemusíte se tímto faktem znepokojovat, ale např. v Céčku je nutné použít typ long long int.
Formát výstupu: Vypište číslo, které reprezentuje počet vyrostlých dýní za T dní.
3 2 -1 3 4
10
38-Z2-3 Písmenková polévka (12 bodů)
Kevin a Sára šli spolu na oběd do školní jídelny. Protože na oběd dnes uvařili písmenkovou polévku, jejich diskuze nevyhnutelně vedla k tomu, že z písmenek v polévce zkoušeli skládat slova. Když se Kevin podíval na svůj talíř, všiml si písmenek T, K, O, L, E, a hned jej napadlo slovo „KOTEL“. Sára však oponovala, že to je přece „LOKET“.
Po Sářině odpovědi hned chytl Kevina nápad. Kolik slov může vytvořit jen z daných písmenek? Rychle vytáhnul z batohu svůj notebook, položil jej vedle talíře a otevřel si slovník českých slov. Pohledem na jeho velikost však pochopil, že to nezvládne sám.
Pro Kevina je alespoň jednoduché ze slovníku vytáhnout všechna slova správné délky. Na vás je, abyste z těch slov našli všechna taková, která lze z vybraných písmenek v polévce vytvořit.
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 celé číslo N – počet slov ve slovníku. Následuje N řádků, každý obsahuje jedno slovo. Po těchto N řádcích je ještě jeden řádek s písmenky, z nichž hledáme všechna možná slova.
Slibujeme, že všechna slova ve slovníku jsou stejně dlouhá a skládají se pouze z malých písmen anglické abecedy.
Formát výstupu:
Vypište všechna slova ze slovníku, která lze sestavit, každé na vlastním řádku, v libovolném pořadí.
6 loket hroch devet otekl vedet kotel tkole
kotel loket otekl
38-Z2-4 Těžká raketa (14 bodů)
Dneska je velký den. Po měsících návrhů a zkoušek je raketa připravená ke startu. Jenže když Kevin s Bobem Kermanem koukali na poslední kontroly, zjistili, že palivo je těžší, než měli v plánu. Celá konstrukce teď táhne víc dolů, než motory dokážou vyrovnat.
Na rampě není času nazbyt. Naštěstí má raketa navrženy odpojitelné části: v nouzi je lze odřezat a poslat dolů, aby zbytek mohl pokračovat. Jenže některé odpojené části obsahují motory – pokud je uřízneme špatně, můžeme přijít o tah nebo ztratit stabilitu. Vaším úkolem je najít, které části odříznout, aby raketa byla schopna vzlétnout.
Pro jednoduchost si představme raketu jako binární strom. V listech jsou motory, které dávají raketě tah (můžeme je chápat jako „zápornou váhu“, tedy snižují celkovou hmotnost), a vnitřní vrcholy tvoří konstrukci, která má kladnou váhu. Když odřízneme podstrom v určitém místě, celý ten podstrom zmizí z rakety a přijdeme také o tah z motoru.
Úkolem je vybrat množinu podstromů k odříznutí tak, aby výsledná váha rakety byla záporná (a raketa mohla vzlétnout). Váhu zjistíte součtem vah všech vrcholů od listů až po kořen. Pomůžete Kevinovi a Bobovi najít algoritmus, který zjistí, jaké podstromy odříznout, nebo jestli to nejde?
Toto je teoretická úloha. Není nutné ji programovat, odevzdává se pouze slovní popis algoritmu. Více informací zde.