Druhá série začátečnické kategorie třicátého páté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 35. 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, řešit můžete začít i v případě, kdy jste se nezúčastnili první série. Ty nejúspěšnější z vás na jaře pozveme na týdenní soustředění (pokud to aktuální situace dovolí), na kterém se toho spoustu dozvíte a zároveň si užijete hromadu neopakovatelné zábavy.
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 11. prosince ve 32:00 (tedy další ráno v 8:00), praktické úlohy za třetinu bodů až do 18. prosince
- 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
35-Z2-1 Párty (9 bodů)
Kevinovi rodiče odjíždějí na krátkou dovolenou a Kevin zůstává sám doma. Přemýšlí, co by si počal. I napadne ho, že by mohl pozvat všechny své kamarády a uspořádat netriviálně velkou párty. Rozeslal tedy hromadu pozvánek. Ale protože je párty uspořádaná docela narychlo, tak se každý z kamarádů rozhodl, kolik musí být na párty účastníků, aby se mu vyplatilo změnit plány a přijít.
![](/img/hippo_party.png)
Párty probíhá následujícím způsobem: Na začátku je v domě jen Kevin, který má dost práce s last-minute organizací, a nemá čas se párty účastnit. Na párty je tedy 0 účastníků. Některým jeho kamarádům může stačit i to, a tak dorazí a informují zbytek pozvaných. Ti pokud nyní vidí, že na párty je dost lidí, se také rozhodnou přijít. A tak se to celé opakuje, dokud buď nejsou všichni na párty, nebo pro všechny ostatní je párty příliš malá.
Bohužel Kevin nestíhá přípravu, a tak nemůže mít přehled o tom, kolik je na párty lidí. Nicméně potřebuje připravit pro každého kamaráda odpovídající počet řízků. Pomůžete mu zjistit počet účastníků?
Známe počet rozeslaných pozvánek (N) a od každého kamaráda známe minimální počet účastníků, za jakého je ochoten přijít. Pomozte Kevinovi zjistit, kolik kamarádů se na párty dostaví.
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 uvedené číslo N, které odpovídá počtu pozvaných kamarádu. Na každém z následujích N řádků je uvedeno, kolik musí být na párty kamarádů, aby daný kamarád přišel.
Formát výstupu: Na samostatný řádek vypište, kolik se na párty dostaví kamarádů.
5 3 1 0 5 0
4
Kamarádi 3 a 5 přijdou hned. Nyní jsou na párty 2 účastníci, a tedy se rozhodne přijít kamarád 2, a po něm už i kamarád 1. Nyní máme celkem 4 účastníky, což kamarádovi 4 nestačí, tedy tohle je finální počet účastníků.
35-Z2-2 Železnice (14 bodů)
Ve městech Xaverov a Yndyanapolis začala zlatá horečka. Železniční společnost Hrochrail totiž v každém z měst rozšířila zvěsti o tom, že v druhém z nich se nachází zlato. Chtěla tak uměle stimulovat poptávku.
![](/img/hippo_jerab.png)
Nyní již jen stačí postavit mezi městy Xaverov a Yndyanapolis železnici. Stavba železnice přes louku stojí 1 zlatý prut a skrz horu K zlatých prutů (K > 0). Kolik zlatých prutů je třeba zaplatit, aby se železnice dala postavit?
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 najdete celá čísla R, S a K, oddělená mezerami.
Na dalších R řádcích následuje mapa oblasti, kde na každém řádku je S znaků.
Každý tento znak reprezentuje buďto město Xaverov označené X
, město Yndyanapolis označené Y
, louku označenou .
, anebo horu označenou A
.
Formát výstupu: Na výstup vypište jedno číslo: nejmenší možný počet zlatých prutů, které je třeba zaplatit.
9 7 10 A.X.AAA AAAAAAA A..A... AA...A. .AAAA.. ......A AA.AAA. ..AAAA. AAA.YAA
42
35-Z2-3 Mince (12 bodů)
Sára s Kevinem se po telefonu dohadují, kdo vypere jejich společnou zásobu KSP triček. Chtějí si hodit mincí, ale Sára je na dlouhém výletě a minci má u sebe jen Kevin, který si hoví doma. Sára určí, kolikrát má Kevin mincí hodit a také přesně kolik orlů mu má padnout, aby praní připadlo na Sáru. Sára se ale bojí, že ji Kevin přelstí, a raději počítá, kolikrát mu padne stejná strana mince v řadě, a pokud se to stane mockrát za sebou, nebude Kevinovi věřit, že nepodváděl, a výsledek neuzná. Vymyslete posloupnost hodů, které má Kevin Sáře nahlásit, aby se vyhnul praní triček a Sára mu uvěřila, že nepodvádí. Sára chce dát Kevinovi šanci, takže posloupnost splňující parametry vždy existuje, a tedy Kevin má vždy šanci vyhrá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 vstupu dostanete na jednom řádku tři čísla oddělená mezerou. Počet hodů N, které má Kevin vykonat, počet orlů O, který mu musí padnout, aby vyhrál, a počet K stejných symbolů, které když padnou v řadě, nařkne Sára Kevina z podvodu.
Formát výstupu: Vypište na jeden řádek N znaků
podle toho, co má Kevin Sáře nahlásit.
P
jako panna nebo O
jako orel.
7 5 3
OOPOPOO
35-Z2-4 Supervěž (9 bodů)
„Pokud nemůžeš vyhrát, změň pravidla.“ – Hannibal, když překročil Alpy na stádu hrochů a vtrhl do Říma (zřejmě).
Tohle přísloví si nyní demonstrujeme na celkem nevinné hře šachů. Jelikož jsme se nechtěli nechat zahanbit před kamarády, šli jsme s nimi hrát hroší šachy na opravdu veliké šachovnici. Šachy ale hrát neumíme, proto jsme brzy začali prohrávat. Teď už nám v rukávu zbývá jen jeden trik: výbušná vež. Tu nenápadně umístníme někam na šachovnici, a než se kdokoliv nadá, vež exploduje, čímž efektivně znemožní ve hře pokračovat. To už pak nějak svedeme na kontumační remízu.
Na vstupu máme šachovnici rozměrů N ×N, která se skládá z volných políček a políček obsazených figurami. Na libovolné volné políčko šachovnice chceme umístit výbušnou věž. Vež exploduje tak, že z ní odletí čtyři části, každá jedním ze směrů rovnoběžných s osami šachovnice (tedy nahoru, dolů, doprava a doleva). Tyhle části pak smetou všechny figurky, které jim stojí v cestě. Výbušnou věží samozřejmě chceme způsobit co největší škody co do počtu zasáhnutých figurek.
Najděte souřadnice pole, na které je nejlepší výbušnou vež umístit. Pokud je možností více, vypište libovolnou z nich.
Toto je teoretická úloha. Není nutné ji programovat, odevzdává se pouze slovní popis algoritmu. Více informací zde.
Praktický kurz programování
![Praktická opendata úloha Praktická opendata úloha](/img/sign_opendata.png)
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í.