První série začátečnické kategorie třicátého sedmé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 první série 37. 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 20. října ve 32:00 (tedy další ráno v 8:00), praktické úlohy za třetinu bodů až do 27. října
• 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

• 37-Z1-1: Počet slov
• 37-Z1-2: Státy
• 37-Z1-3: Čekání na tramvaj
• 37-Z1-4: Hloubka vrcholů ve stromu

37-Z1-1 Počet slov (8 bodů)

Je léto, sluníčko svítí a Sára si užívá zasloužený odpočinek u Hrošího jezera. Celý den nemusí nic dělat, a tak se jen opaluje a čte. Hltá jeden text za druhým, až je k neuvěření, kolik toho za celé léto stihne přečíst. Sára čte romány, novinové články, seznamy ingrediencí na zadních stranách sladkostí, básně, vzorové zdrojáky úloh KSP z minulých sérií, dlouhé chemické vzorce, krátké chemické vzorce, letáky ze supermarketu a další roztodivné texty.

Soudit Sářin čtecí výkon jen podle počtu samotných textů či přečtených stránek tak nemá moc velký smysl. Místo toho se Sára rozhodla posoudit svou čtecí zdatnost tak, že spočítá, kolik slov stihla za celé léto přečíst. Takovou mravenčí práci by ale nejspíš dělala až do Vánoc, a tak si Sára žádá o vaši pomoc.

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 jeden dlouhý řádek složen z ASCII znaků, tj. písmena anglické abecedy bez diakritiky, číslice, interpunkční znaménka a další. Jako slovo se počítá souvislý úsek písmen anglické abecedy. Kupříkladu ahoj je jedno slovo, ale ahoj2riso jsou 2 slova.

Formát výstupu: Na výstup vypíšete jediné číslo – počet slov, které Sára za léto přečetla.

*Ahoj~)0JAK%8SE^mas?

4

Řešení

37-Z1-2 Státy (10 bodů)

„Z Arizony na sever do Utahu, potom na východ do Colorada, pak zase zpátky do Utahu, …Teda, těch států ale bylo, viď Sáro.“ Kevin se snažil dopočítat všech zemí, které navštívili společně se Sárou při svém prázdninovém výletu do Spojených států. „Určitě jich bylo aspoň 30!“ vyhrkla Sára. „Tolik jich určitě nebylo, nejvýš 29,“ oponoval jí Kevin. „A víš co, pojďme to spočítat přesně. Vždyť máme mapu států a víme, jakými směry jsme chodili.“

Vaším úkolem bude nyní rozsoudit Kevina se Sárou, tedy určit, kolik států ve skutečnosti navštívili. Naštěstí je mapa států velmi jednoduchá. Vypadá jako obdélníková tabulka a každé políčko je územím nějakého státu. Dále víte, odkud Kevin se Sárou vyšli a znáte posloupnost jejich pohybů. Ty jsou pouze do čtyř směrů: na sever, na jih, na východ a na západ.

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 řádků dostanete pět celých čísel R, S, r, s, l. R značí počet řádků, S počet sloupců tabulky. Malá písmena r a s značí počáteční pozici Kevina se Sárou: r je číslo řádku počítáno zeshora, s je číslo sloupce počítáno zleva. Obě jsou indexována od 0. Následuje popis mapy: Na každém z následujících R řádků dostanete S názvů států oddělených mezerou. Název státu je posloupnost maximálně 6 znaků neobsahující mezeru. Na posledním řádku dostanete l znaků, které vyjadřují posloupnost pohybů. Každý je jedním ze znaků <, ^, > a v. V uvedeném pořadí znamenají pohyb na západ, sever, východ a jih. Slibujeme, že výlet nikdy nevede mimo mapu.

Formát výstupu: Na výstup vypište počet unikátních států, které Kevin a Sára navštívili. (Protože to tak je i ve skutečném světě, může ke státu patřit i nesousedící území, tedy exkláva.)

2 3 0 2 5
A B C
D E B
v<<>^

4

Kevin se Sárou začnou výlet ve státě C, pokračují na jih do B, poté následují státy E a D, pak se vrátí do E a skončí ve státě B. Celkem tedy navštívili 4 různé státy.

Řešení

37-Z1-3 Čekání na tramvaj (12 bodů)

Kevin se o prázdninách rozhodl podívat do botanické zahrady. Naštěstí se tam dopraví jednoduše, neboť mu jede přímá tramvaj. Došel tedy na zastávku a čekal.

Když takto čekal už 17 minut, začalo mu to být divné. Mezi tramvajemi přece tak velké intervaly nejsou, nebo snad ano? Trochu naštvaně došel k jízdnímu řádu a začal v něm hledat. Ukázalo se, že přišel zrovna ve chvíli, kdy dlouho žádná tramvaj nejela. Že by měl až takovou smůlu? Teď jej zajímá, jestli vůbec mohl přijít v horší dobu.

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 číslo N, počet tramvajových linek, které jezdí na danou zastávku. Následuje 2N řádků, kde každé dva řádky popisují jízdní řád jedné linky. Na prvním z nich je číslo P_i, počet tramvají této linky, které za den zastávkou projedou. Na druhém je pak P_i časů jednotlivých příjezdů zapsaných jako počet sekund od půlnoci.

Časy jsou zapsané ve vzestupném pořadí. Může se stát, že ve stejný čas přijede více tramvají.

Formát výstupu: Odpovědí je nejdelší časový úsek, kdy žádná tramvaj nejede; uvažujeme všechny linky dohromady. Na jeden řádek vypište čas začátku tohoto úseku a jeho délku, obojí v sekundách.

Pozor, nejdelší úsek může trvat přes půlnoc! (Jeden den trvá 86 400 sekund a tramvaje jezdí každý den stejně.) Slibujeme, že nejdelší úsek je unikátní.

2
3
32000 40000 61000
4
20000 32000 44000 84000

61000 23000

Řešení

37-Z1-4 Hloubka vrcholů ve stromu (14 bodů)

Albert zaléval svůj velikánský posvátný strom, když v tom si všiml, že mu jeden list uschl a spadl na zem. Proto začal přemýšlet, jak daleko od kořenů jsou asi jednotlivé listy. Třeba támhleten ve tvaru srdíčka s výraznými žilkami je určitě pět metrů od kořenů, ale ten nažloutlý ve tvaru srdíčka zase 7 metrů od kořenů. Když takhle určil svůj 157. list, uvědomil si, že by ho vlastně zajímala vzdálenost nejen všech listů, ale také každé větvičky. Pomůžete Albertovi určit, jak daleko od kořenů jsou?

Počítejte s tím, že máte v paměti pole s vrcholy stromu, kořen je na začátku pole. V každém vrcholu máte uložený index otce v poli, neboli máte jednosměrný odkaz z každého vrcholu na vrchol, který je od něj o 1 blíž ke kořeni, ne však naopak. Kořen žádný takový odkaz nemá. Vaším cílem je do každého vrcholu vepsat, kolik hran je mezi ním a kořenem stromu.

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í