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 ř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

• 35-Z2-1: Párty
• 35-Z2-2: Železnice
• 35-Z2-3: Mince
• 35-Z2-4: Supervěž

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.

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

Řešení

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.

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

Řešení

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

Řešení

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í

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

Řešení