Pátá 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 páté 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í!

Zadání úloh

Praktická opendata úloha36-Z5-1 Alergie (8 bodů)

Jaro už pomalu klepe na vrata a Kevin s jeho kamarády by se po dlouhé zimě rád vydal na výlet. Na jaře začíná kvést spoustu zeleně a tato výprava do přírody jim jistě vyčistí hlavu. Naneštěstí je ale zeleň přesně to, co Kevina a jeho partu trápí. Každý z nich je na něco alergický. Pokud by se někdo vydal do oblasti, kde se vyskytuje jeho alergen, tak by celý výlet pšíkal a smrkal a moc by si ho neužil, takže raději nepojede.

Kevin má seznam svých N kamarádů s jejich alergeny. Také už udělal průzkum L lokalit, u kterých zjistil, jaké se tam vyskytují alergeny. Rád by naplánoval výlet někam, kam pojede co nejvíce jeho kamarádů, kteří nejsou alergičtí na nic v dané oblasti. Pomůžete mu?

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 čísla N a L oddělená mezerou. Následuje 3N řádků. Každá trojice popisuje jednoho člověka a obsahuje příjmení, počet alergenů a alergeny oddělené mezerami. Poté následuje 3L řádků. Každá trojice popisuje jednu lokalitu a obsahuje jméno lokality, počet alergenů a alergeny oddělené mezerami.

Jména lidí a lokalit mohou obsahovat mezery. Alergeny jsou přirozená čísla.

Formát výstupu:

Vypište na jednom řádku počet lidí a jméno lokality, do které se Kevin a jeho přátelé mají vydat, aby jich jelo co nejvíc. Oddělte položky mezerou. Pokud je takových lokalit víc, vypište tu, která je ve vstupu uvedena nejdříve.

Ukázkový vstup: 
2 2
Novakova
3
1 4 5
Cerny
2
1 3
Samarinda
2
2 3
Calgary
1
2
Ukázkový výstup: 
2 Calgary

Řešení

Praktická opendata úloha36-Z5-2 Pletení pomlázky (10 bodů)

Vašek si chce na Velikonoce uplést pomlázku. Když sbíral proutky, našel jeden obzvláště pěkný s květem na konci. Vašek chce tento proutek umístit tak, aby v pomlázce vyniknul. Pomozte mu zjistit, kde květ skončí po upletení pomlázky.

Pomlázka se skládá z K proutků. Na začátku jsou všechny položené paralelně vedle sebe a ten s květem je na pozici X. Pletení se skládá z N stejných kroků postupujících od spodního konce. V každém se proutky přes sebe přehýbají, čímž se přehází jejich pořadí – pro každou pozici máme určené, kam se daný proutek přesune.

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 počet proutků K, počet kroků N a počáteční pozici X. Na dalším řádku dostanete K čísel popisujících jeden krok pletení. Číslo na pozici Y říká, kde skončí Y-tý proutek po jednom kroku. Všechny pozice (X a celý druhý řádek) jsou indexované od nuly.

Formát výstupu: Vypište jedno číslo – na jaké pozici bude X-tý proutek po N krocích pletení.

Ukázkový vstup: 
6 3 4
5 2 1 0 3 4
Ukázkový výstup: 
5
Pomlázka

Řešení

Praktická opendata úloha36-Z5-3 Toruslice (12 bodů)

Velikonoce se letos nesly ve znamení krásných barevných kraslic, zanechávajících ve všech pozitivní náladu a inspiraci. Jelikož Zuzčiny umělecké sklony neznají hranic, rozhodla se do příštího roku natrénovat malování kraslic nejenom zvenku, ale taky zevnitř. Detaily technické realizace zřejmě jednoduše vyřeší pak, proto se teď začala zabývat navrhováním hezkých mnohobarevných vzorů.

Ani to ale rozhodně není jednoduché. Každá kraslice má totiž vnější a vnitřní část, které jsou vizuálně propojeny dvěma dírami na obou "pólech" kraslice. Z topologického hlediska tedy tvoří torus – tvar koblihy s dírou uprostřed, prstence, nebo i tunelu. I když si tedy celou síť téhle "toruslice" Zuzka reprezentuje obdelníkovou mřížkou (aby se jí dobře navrhovala v počítači), musí myslet na to, že čtverečky na pravém a levém okraji budou ve výsledku sousedící, a stejně tak vrchní a spodní čtverečky.

Zuzka už má přichystaných několik různě velikých návrhů, ve kterých má zakreslené bílé čtverečky tvořící základní obrysy. S těmi je velice spokojená a měnit je nechce. Chtěla by ale zjistit, kolik dalších barev může při obarvování použít, pokud každou souvislou plochu obarví jinou barvou (aby byly toruslice co nejhezčí, musí samozřejmě být co nejbarevnejší).

Potřebovala by tedy od vás, abyste jí pomohli spočítat, kolik se v jejím návrhu nachází souvislých prázdných oblastí. Za sousedící přitom považujeme jenom čtverečky sdílející stejnou hranu, nikoliv dotýkající se rohem.

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 S a V – šířku a výšku obdelníku reprezentujícího jednu toruslici.

Následuje V řádků, každý dlouhý S znaků # (mřížka, reprezentující čtvereček zaplněný bílou barvou) nebo . (tečka, reprezentující prázdný čtvereček).

Formát výstupu: Na výstup vypište jedno číslo – počet barev, které Zuzka potřebuje na obarvení dané toruslice. Nezapomeňte na znak konce řádku.

Ukázkový vstup: 
8 6
.#...##.
#.##.#.#
.#.#..#.
##.#..##
....#.#.
#...#.#.
Ukázkový výstup: 
4

V tomto případě tvoří teměř všechna volná políčka jednu souvislou oblast, zbývající tři oblasti jsou dvě velikosti jedna (čtvereček na [2, 2] a další na [7, 2]) a jedna velikosti dva (čtverečky na [1, 3] a [8, 3]).

Řešení

Teoretická úloha36-Z5-4 Koledování (14 bodů)

Je Velikonoční pondělí. Venku kvetou stromy, roste kvítí, příroda se raduje ze života, který se v ní po krušné zimě opět probouzí. A Kevin se v tomto krásném dni rozhodl věnovat tradičním zvykům, jimž se v jeho vesnici věnoval již jeho otec, děd i praděd. Rád by obešel domy všech kamarádek, jež ve vesnici žijí spolu s ním.

Má to ale drobný problém – kamarádky se tradicím věnují se stejnou vervou, a proto každého, kdo přijde po poledni, bez rozpaků polejí vědrem vody. Tomu by se Kevin rád vyhnul, proto si přivstal velmi brzy ráno. I tak ale nestihne navštívit všechny kamarádky.

Kevinovo město má jednoduchý tvar přímky, domy stojí vedle sebe a pozice každého z nich je jednoznačně určena jeho vzdáleností od počátku města. Kevin chodí stále stejně rychle a dobu, kterou stráví v domech kamarádek, můžete zanedbat. O dvanácté ale už musí být zpátky v bezpečí svého domu.

Na vstupu dostanete souřadnice domů, v nichž bydlí Kevinovy kamarádky, a souřadnici Kevinova domova. Souřadnice dostanete seřazené od nejmenší po největší. Také dostanete informaci o tom, kolik času zbývá Kevinovi do pravého poledne a jakou rychlostí cestuje. Pomozte mu najít cestu, kterou stihne ujít za zbývající čas, navštíví během ní co nejvíce kamarádek a v poledne bude zpátky doma.

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

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

Řešení