První série začátečnické kategorie třicátého osmého ročníku KSP

Celý leták v PDF.

Nový školní rok je tady, a s ním přichází i nový ročník KSP-Z! Začátky mohou být někdy náročné, a proto jsme tu, abychom vám pomohli. Pokud 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 první 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í!

Zadání úloh

Praktická opendata úloha38-Z1-1 Odchycení zpráv (8 bodů)

Kevin a Sára hrajou proti sobě na táboře hru na špionáž a Kevin se rozhodl, že bude opatrný a svoje zprávy zašifruje. Konkrétně, že vezme každé písmeno ve zprávě a nahradí ho následujícím písmenem v anglické abecedě. Z písmene a se stane b, z h je i, a z se zapíše jako a. Například slovo zebra zašifrujeme jako afcsb.

Kevin ale bohužel nepočítal s tím, že Sára velmi dobře zná jak tuto šifru, tak Kevina. Sára teď potřebuje pro hru najít všechny jeho zprávy, kde zašifroval slovo poklad. Výrazně ale podcenila, kolik vzkazů Kevin posílá. Desítky, stovky, tisíce! Sama to nezvládne, pomůžete jí?

Na vstupu dostanete seznam zašifrovaných zpráv a máte za úkol pro každou zprávu rozhodnout, zda po dešifrování obsahuje slovo poklad.

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 zpráv/řádků textů, které jsou na vstupu. Potom bude následovat N řádků textu, skládající se z malých písmen anglické abecedy.

Formát výstupu: Pro každý řádek vypište ANO pokud se na něm po dešifrování vyskytuje slovo poklad, jinak vypište NE.

Ukázkový vstup: 
5
tdipwbntftqplmbefnqpewpev
pqfsbdflvmpwzcmftlnvafabdju
ajusbcveftmvofdopnjtuznsblz
nbsjtftbibpeqsbizbaqplmbeop
abaobnfoboqplmftnpsbmlz
Ukázkový výstup: 
ANO
NE
NE
ANO
NE

Vysvětlení: Po dešifrování dostáváme:

schovamsespokladempodvodu
operacekulovybleskmuzezacit
zitrabudeslunecnomistymraky
marisesahaodprahyazpokladno
zaznamenanpoklesmoralky

Slovo poklad se vyskytuje jen v první a čtvrté zprávě.

Praktická opendata úloha38-Z1-2 Zuzčin Standup (10 bodů)

Sociální sítě, pandemie COVID19, umělá inteligence – duševní zdraví člověka je v dnešní době vystaveno těžké zkoušce. Zuzka je ale ženou činu a chce svým kamarádům co nejvíce pomoci. Pořádá proto komická vystoupení, kde zájemce rozveseluje vtipy. Zároveň ale dbá na to, aby každý z jejích vtipů byl opravdu dobrý a nikoho neurazil, a proto si pečlivě vybírá, které vtipy použije, a má vždy jen jednoho posluchače naráz.

Zájemců o Zuzčina vystoupení ale přibývá a Zuzka už dvakrát nedokázala uspokojit všechny pacienty. Pomůžete jí zjistit, kolik nejvíce pacientů dokáže během jednoho dne uzdravit? Zuzka doufá, že když bude cílit na kvantitu uzdravených, zbývajícím se už stihne věnovat odborná lékařská pomoc.

Jako vstup dostanete počet vtipů pro jednotlivá Zuzčina vystoupení a informaci, kolik vtipů musí pacient slyšet, aby byl zdravý na duši. Vystoupení Zuzka nikdy neopakuje (to by se negativně podepsalo pro změnu na jejím duševním zdraví), ale pacienti se klidně mohou vystřídat v průběhu, nemusí si dílo doposlechnout do konce.

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 jsou dvě čísla N a M – počet Zuzčiných vystoupení a počet pacientů. Druhý řádek obsahuje počet vtipů v jednotlivých Zuzčiných vystoupeních. Třetí řádek obsahuje počet vtipů, které musí slyšet jednotliví pacienti, aby byli zdraví na duši.

Formát výstupu: Na výstup vypište jedno číslo, které značí maximální počet pacientů, které Zuzka dokáže během dne uzdravit.

Ukázkový vstup: 
4 3
18 2 3 7
25 1 10
Ukázkový výstup: 
2

Zuzka má k dispozici 4 vystoupení, na které si celkově připravila 30 vtipů. Pacienti potřebují 25, 1 a 10 vtipů k uzdravení. Jedno z možných řešení je, že Zuzka nejdříve uzdraví pacienta s 10 vtipy a pak dalšího pacienta s 1 vtipem. Na třetího pacienta, který potřebuje 25 vtipů, už jí nezbývá dostatek vtipů, takže dokáže uzdravit maximálně 2 pacienty. Alternativně by Zuzka mohla třeba nejdříve uzdravit pacienta s 1 vtipem a pak pacienta s 25 vtipy, čímž celkem uzdraví také dva pacienty.

Praktická opendata úloha38-Z1-3 Superhroší věže (12 bodů)

Sára sedí zamyšleně u okna. Pozoruje, jak za sebou kapky deště stékající po okenních tabulkách nechávají úzké klikaté cestičky. I v létě občas zaprší. A tak dnes Sára sedí doma a nudí se. Hmmm, co by tak asi mohla dělat? Už to mám! Zahraje si přeci svou novou počítačovou hru – Super Hroch! A tak hned Sára žhaví svůj počítač a spouští první level hry. Se svou postavičkou pobíhá po herní ploše a vyhýbá se nepřátelům.

Mezi ty nejzákeřnější z nich patří vysokánské superhroší věže. Jde o věže z na sebe naskládaných hrochů, které se pohybují ve velké obdélníkové mřížce mezi zdmi. Na začátku hry se v mřížce pohybují jen jednotliví hroši (tedy hroší věže výšky 1). Pokaždé, když se dvě věže srazí, se hroši v obou věžích přeskládají do jedné ještě vyšší věže.

Čím vyšší superhroší věž je, tím chaotičtěji se pohybuje a tím je pro Sáru obtížnější se jí vyhýbat. Sáru by tak zajímalo, s jak vysokými věžmi se bude muset po určité době ve hře potýkat.

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 dvě čísla M a N určující počet řádků a sloupců mřížky. Na druhém řádku je pak číslo K – počet hroších věží (všechny výšky 1), které se na počátku nacházejí v mřížce. Následně na třetím řádku dostanete číslo T udávající počet jednotek času, které Sára stráví ve hře. Následuje M řádků, každý s N znaky, s počátečním stavem mřížky.

Možné znaky v mřížce jsou následující:

Jeden krok superhroší věže vypadá následovně: pokud před věží není zeď ani okraj mřížky, pak postoupí o krok dopředu. Jinak zůstane na místě a otočí se o 90 stupňů vlevo. Každá věž vykoná jeden krok za jednu jednotku času a tyto kroky probíhají souběžně. Pokud by se v jeden moment mělo více věží ocitnout na jednom políčku zároveň, stane se z nich jedna věž orientovaná směrem nahoru, jejíž výška je rovna součtu výšek původních věží.

Například pokud bychom měli na vstupu řádek s >.<, pak se z těchto dvou věží po jednom kroku stane jediná věž výšky 2 a orientací nahoru. Naopak ale pokud bychom na vstupu dostali řádek s ><, pak se po jednom kroku tyto dvě věže nesrazí, nýbrž si jen vymění místa.

Formát výstupu: Na výstup vypište jediný řádek se vzestupně setříděnými výškami superhroších věží po T krocích. Jednotlivá čísla oddělte mezerou.

Ukázkový vstup: 
4 5
4
2
<...#
..V#.
A...#
..A..
Ukázkový výstup: 
1 1 2

V prvním kroku se dvě věže v pravé části srazí a vytvoří novou věž výšky 2. V druhém kroku se věže v levé části minou a zůstanou tak obě na své původní výšce 1.

Teoretická úloha38-Z1-4 Sousedi ve stromu (14 bodů)

Začaly prázdniny, venku vedro jako na Sahaře a Kevin raději zůstává celé dny zavřený doma. Komu však toto extrémní klima svědčí, je Kevinův nový přírustek do jeho zahrádkářské kolekce – nově objevená bylina zvaná Chromatis Maxima. Tato pompézní rostlinka je speciální hlavně svými barevnými květy. Tu je modrý, tam je červený, onde zas tyrkysový. Kevin ani neumí všechny ty barvy pojmenovat.

Tuto květinu si Kevin nepořídil náhodou. Jakožto milovník čajových dýchánků si nenechal ujít informaci o tom, že odvar z jejích květů má hojivé účinky. Jaký tento účinek zrovna bude, prý přesně odpovídá barvě květu, který k přípravě čaje použijeme.

Má to však jeden háček. Dle legend blahodárné účinky pramení z nedetekovatelných proudů energie, které květy jednotlivých barev vyzařují. Pokud nastane, že dva květy stejné barvy vyzařují příliš blízko vedle sebe, jejich frekvence se navzájem vyruší, celá rostlina se tím destabilizuje a ztrácí své léčivé vlastnosti. Pomůžete Kevinovy takové květy nalézt, aby je mohl včas zastřihnout?

Kevinovu květinu si jde představit jako shluk květů pospojovaných stonky. Každý květ je v nějaké hladině: na první hladině je jen jediný květ (pomyslný kořen květiny), z něj vyrůstají květy na druhé hladině, z nich květy na třetí hladině, a tak dále. Chromatis Maximas je vskutku pozoruhodná, a tak všechny květy na jedné hladině rostou vždy ve stejné výšce.

Na vstupu dostanete popis Kevinovy květiny zadaný seznamem květů. Pro každý květ znáte jeho identifikátor, přirozené číslo B označující jeho barvu, a uspořádaný seznam identifikátorů květů, které z něj vyrůstají, v pořadí zleva doprava.

Vaším úkolem je navrhnout algoritmus, kterým detekujete, zda existují dva květy se stejným číslem B na stejné hladině stromu, nacházející se na této hladině bezprostředně vedle sebe. Pozor, že květy počítáme jako vedlejší i pokud bezprostředně nevyrůstají ze stejného květu.

Na obrázku výše jako vedlejší počítáme dva červené vrcholy na předposlední vrstvě a žádné jiné.

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

K řešení této úlohy se Ti může hodit prostudovat si sekci o grafech v naší základní kuchařce a taky naši grafovou kuchařku.

Praktický kurz programování

Praktická opendata úloha

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

Praktická opendata úloha

Ř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š:

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í.