Čtvrtá 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 čtvrté 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 31. března ve 32:00 (tedy další ráno v 8:00), praktické úlohy za třetinu bodů až do 7. dubna
- Odevzdávání: elektronicky přes Odevzdávátko
- Jak sepsat řešení: viz ukázková úloha MO-P
- Dotazy ohledně zadání: posílejte na ksp@mff.cuni.cz, nebo se ptejte na Discordu KSP.
Zadání úloh
36-Z4-1 Sněhuláci (8 bodů)
Kevin se vracel s kamarády ze školy. Právě přecházeli lyžařskou sjezdovku (těch je v Hroším Týnci mnoho), když narazili na velkou haldu různě velkých sněhových koulí. Ty tam byly připraveny jako náboje do sněhových děl, sněžit ale začalo samo od sebe a koule najednou nebyly potřeba. Po krátké, ač usilovné debatě se správcem sjezdovky dostal Kevin s kamarády povolení dělat si s koulemi, co chtějí.
Jakožto velmi soutěživá skupina se rozhodli udělat si soutěž ve stavění sněhuláků. Ale ne tak libovolných sněhuláků. Musí to být pořádní sněhuláci. Takový pořádný sněhulák se skládá ze tří koulí nad sebou, přičemž spodní koule musí být větší než prostřední a prostřední koule musí být větší než vrchní.
V zápalu soutěže ale začaly koule docházet a účastníci se o ně začali přetahovat. Kevin se tedy rozhodl začít soutěž od začátku a každému účastníkovi přiřadit tři koule tak, aby se z nich dal postavit sněhulák. Každou kouli lze pochopitelně použít jen v jednom sněhulákovi. 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 vstupu dostanete číslo N, počet sněhových koulí.
Na dalším řádku pak bude N navzájem různých velikostí koulí oddělených mezerou.
Formát výstupu: Na první řádek vypište jedno číslo K – maximální počet sněhuláků, které jde postavit. Poté vypište K řádků, na každém z nich trojici sněhových koulí, ze kterých lze sněhuláka vyrobit. Koule vypisujte v pořadí od největší po nejmenší. Pokud je řešení více, vypište libovolné z nich.
9 7 4 3 2 5 8 1 10 6
3 10 2 1 6 5 4 8 7 3
36-Z4-2 Sáňkování (10 bodů)
Sára se zrovna probudila, že vyrazí do školy, hledí z okna a co nevidí. Všude kolem je tolik sněhu, že pokrývka sahá až po střechy zaparkovaných aut a nic nenasvědčuje tomu, že by město bylo schopné vyslat dostatek pluhů a občany tak vysvobodit. Někteří by se možná situace zalekli, ale Sáře, jakožto rozené horalce, se rozsvítily oči a hned šla ze skříně vyštrachat své sáňky, sněžnice a cepín, že se do školy dostane děj se co děj. K jejímu zklamání ale, než stihla svou výbavu posbírat, přišel e-mail od ředitele školy, že se výuka z provozních důvodů ruší. Sára chvilku smutnila, že nakonec své výbavy nevyužije, ale pak si vzpomněla, že na matfyzu právě skončilo zkouškové a přednášející, kteří už se po delší přestávce nemůžou dočkat, že zase začnou přednášet, nic jen tak nezastaví. Tak Sára popadla své vybavení, vykutala si cestu ven ze zapadaných dveří a už sviští pražskými ulicemi na sáňkách.
Bohužel cesta není jen tak jednoduchá. Malá Strana je sice v ďolíku, ale než se tam dostane, bude se muset ještě vyškrábat na Petřín, odkud už sjede dolů na sáňkách. Škrábání se do kopce zabere spoustu času a Sára by chtěla vědět, jestli stihne přednášku, kterou si vyhlídla. Pomůžete jí zjistit, jak rychle se na matfyz dostane?
Celá Sářina cesta lze popsat jako posloupnost rovinek v různých nadmořských výškách. Když jede Sára z kopce, nabírá rychlost, když jede do kopce, rychlost ztrácí. Když se pokusí vyjet na kopec, na který nemá dostatečnou rychlost, sklouzne zpátky na předchozí rovinku, kde se zastaví a musí šlapat nahoru. Na další rovince může zase nasednout na sáňky a pokračovat v cestě. Sáňky jsou to samozřejmě ideální, takže na ně nepůsobí tření a veškerá rychlost, kterou naberou, se využije pro vystoupání na následující kopce. Také jsou dost rychlé, aby se čas na nich strávený dal zanedbat a proto nás zajímá jen počet výškových metrů, které musí Sára nastoupat pěš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 vstupu dostanete číslo N a pak N čísel, která reprezentují nadmořské výšky jednotlivých rovinek, přes které se Sára potřebuje dostat. Výšky jsou nezáporné.
Formát výstupu: Jedno číslo, které reprezentuje počet výškových metrů, které musela Sára po cestě nastoupat pěšky.
8 12 9 11 8 14 13 12 13
6
Vysvětlení ukázkového vstupu: Sára začíná v nadmořské výšce 12, odkud sklouzne na rovinku výšky 9 a nabere tak rychlost 3. Na následující rovinku výšky 11 se tak zvládne vyhoupnout a zbyde jí rychlost 1. Jízdou z 11 na 8 nabere další 3 jednotky rychlosti a má tedy celkem 4. To ale k vyjetí na rovinku výšky 14 nestačí, a proto musí všech 6 metrů vyšlapat. Na 14 pak zase na sáňky nasedne, sjede na 13 a 12, nabere tím celkem 2 jednotky rychlosti, které jí stačí na vyjetí na následující 13 a je u cíle. Jediný případ, kdy musela šlapat je tedy mezi 8 a 14, a našlapala celkem 6 metrů.
36-Z4-3 Náledí (14 bodů)
Kevin a Sára se každé pondělí po cestě do školy potkávají na Hrošínském náměstí, aby spolu mohli před začátkem první hodiny obdivovat místní sochy hroších bohů. Ani toto pondělí nebylo výjimkou. Kevina se Sárou ale čekalo nemilé překvapení. Náměstí přes noc pokrylo náledí a pohybovat se po něm je tak téměř nemožné.
Sára má ale plán, jak se přece jen přes náměstí do školy dostat. Sára se ze své pozice vždy odrazí do jednoho ze 4 směrů a zastaví se až o některou sochu nebo o okraj náměstí. Ze svého místa před sochou pak pokračuje v odrážení dál, až se nakonec dostane do cíle. Dokážete pomocí Sářina plánu najít cestu do školy?
Hrošínské náměstí je tvaru mřížky H ×W. Ve mřížce je označené startovní a cílové políčko. Na náměstí mohou vést i podchody, tato políčka tak mohou být i uprostřed mřížky. Ostatní políčka jsou buďto prázdná, nebo na nich stojí socha. Sára se ze své pozice může odrazit do 4 různých směrů – doleva, doprava, nahoru a dolů. Sára se zastaví o sochu nebo o okraj náměstí a zůstane stát na políčku před ním.
Nás zajímá posloupnost směrů, do kterých se Sára musela odrazit, aby se dostala do cíle. Projitím přes cílové políčko se Sára sama zastaví, nemusí se tak nutně zastavit o sochu nebo okraj náměstí.
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 vstupu dostanete 2 přirozená čísla H a W označující výšku a šířku mřížky. Každý z následujících H řádků obsahuje W znaků reprezentující náměstí. Každý znak reprezentuje jedno políčko:
-
.– Prázdné políčko -
#– Socha -
S– Startovní políčko -
C– Cílové políčko
Formát výstupu:
Na jeden řádek bez mezer vypište posloupnost znaků L, P, N a D
označující odrazy vlevo, vpravo, nahoru a dolů, kterými se Sára dostane ze startu do cíle.
Pokud existuje cest více, vypište libovolnou z nich.
6 5 S.... .#... ..C.. ..... #.... #...#
PDLNP
36-Z4-4 Chata (12 bodů)
Zuzka v zimě ráda běžkuje a letos se vydala na zasněžené pláně Hroších hor. Bohužel se během jednoho svého výletu ztratila a neví, kudy se vrátit na svou horskou chatu. A protože je zapomnětlivá, tak dokonce zapomněla i to, jak se její chata jmenuje.
Naštěstí má k dispozici mapu běžeckých tras v Hroších horách. Mapa je daná seznamem křižovatek s chatami a seznamem cest mezi těmito chatami. Každá cesta má také svoji délku v km. Kvůli vysoké ceně prohrnování tvoří trasy strom, tedy v nich neexistuje žádná kružnice, žádná okružní trasa.
Zuzka ví, na jaké křižovatce se nachází, a také jí její chytré hodinky ukazují, kolik km ujela na cestě ze své chaty na křižovatku, kde právě je. Zuzka jela nejkratší možnou cestou, dá se tedy také říct, že ví, jak daleko je její chata. Pomozte najít Zuzce její chatu.
Toto je teoretická úloha. Není nutné ji programovat, odevzdává se pouze slovní popis algoritmu. Více informací zde.
Praktický kurz programování
Pokud Tě lákají praktické úlohy, ale ještě neumíš žádný programovací jazyk, můžeš se podívat na náš Základní kurz programování, kde se můžeš naučit základy Pythonu: https://ksp.mff.cuni.cz/kurz/.
Zdrojáky praktických úloh
Řešení praktických úloh může být ze začátku složité. Velmi často i nějaká triviální technická chyba ve zdrojovém kódu programu může znamenat, že program vrací špatný výsledek – a některé chyby se ze začátku špatně hledají. Proto Ti nabízíme možnost poslat zdrojový kód programu nějaké úlohy na adresu zdrojaky@ksp.mff.cuni.cz, kde se Ti pokusíme poradit. Do emailu prosím připiš:
- Jakou úlohu by měl program řešit.
- Slovní popis, co by měl program podle Tebe dělat.
Před termínem série Ti nemůžeme radit s algoritmem, ale pomůžeme s odladěním zdrojáku. Po termínu série pak můžeme poradit i s návrhem algoritmu – získáš tak znalosti do dalších sérií.