První série začátečnické kategorie třicátého čtvrté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 34. ročníku KSP-Z, neboli Korespondenčního Semináře z Programování, Začátečnické kategorie. Jedná se o korespondenční soutěž spočívající v řešení jednodušších programátorských úloh, které vychází během školního roku. Zapojit se může každý středoškolák i základoškolák, ty úspěšnější z vás pak na jaře pozveme na týdenní soustředění, na kterém se toho spoustu dozvíte a zároveň si užijete hromadu neopakovatelné zábavy. 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í!
Letos bude v KSP-Z pět sérií po čtyřech úlohách za celkem 220 bodů.
- Termín série: neděle 24. října ve 32:00 (tedy další ráno v 8:00), praktické úlohy za třetinu bodů až do 31. ří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
34-Z1-1 Letopočty (8 bodů)
Kevin se rozhodl vycestovat na Alpha Centauri Prime, ale byl velmi zmatený z místního kalendáře, který se od kalendáře planety Země trochu liší. Jeden rok by tam totiž astronomicky správně měl trvat pouze 42.3125 dne.
Domorodci používají systém, ve kterém má jeden jejich rok 42 dní, ale každý třetí rok je přestupný (a má tedy 43 dní). Výjimku tvoří každý 48. rok, který přestupný není. Jejich kalendář začíná rokem jedna (tedy historicky první přestupný rok byl rok 3).
Pomozte Kevinovi zjistit, kolik dní na Alpha Centauri Prime vlastně zůstane, pokud přijede na začátku roku číslo x a odjede na konci roku číslo y. Započítáváme i dny příjezdu a odjezdu.
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.
Vstup: Vaším úkolem bude zodpovědět N otázek. Na prvním řádku je celkový počet N dvojic roků. Následuje N řádků s dvojicemi celých čísel x,y ≥ 1, kde x ≤ y, x značí rok, na jehož začátku Kevin na Alpha Centauri Prime dorazí, a y značí rok, na jehož konci Kevin odjede. Oba roky se vejdou do 32bitové celočíselné proměnné.
Výstup: N řádků, na každém z nich celočíselný počet dní, které Kevin na Alpha Centauri Prime stráví. Pozor, počet dní se do 32bitové celočíselné proměnné vejít nemusí.
3 47 48 48 51 100 200
84 169 4273
34-Z1-2 Čísla domů (10 bodů)
V Hroší ulici domy nečíslují hezky po řadě, ale postupně podle toho, kdy byl který dům dostavěn.
Čísla domů ale ještě nikde nebyla zveřejněna. Pouze jste v záznamech stavební firmy zjistili přesný čas, kdy byl který dům dostavěn. Rádi byste si s pomocí těchto záznamů čísla domů odvodili sami.
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.
Vstup: Nejprve dostanete jedno celé číslo N – počet domů v ulici. Na následujících N řádcích jsou data a časy dokončení stavby jednotlivých domů v pořadí, v jakém stojí na ulici. Máte zaručeno, že žádné dva domy nebyly dostavěny ve stejný moment.
Každé datum je zadané ve formátu
YYYY-MM-DD hh:mm:ss.
Tedy nejprve pomocí čtyř cifer rok, pomocí dvou cifer měsíc a den.
Dále pak pomocí tří dvojic cifer hodina, minuta a sekunda.
Výstup: Vypište N řádků obsahujících ke každému domu jeho číslo. Čísluje se od 1. Domy vypisujte ve stejném pořadí jako na vstupu, tedy podle toho, jak stojí na ulici.
4 2020-05-15 10:26:57 2020-05-18 17:32:00 2020-04-30 22:11:53 2020-05-18 16:20:15
2 4 1 3
34-Z1-3 Hádání čísel (12 bodů)
Sára si oblíbila hru na hádání čísel. Chce po Petrovi, aby si myslel nějaké číslo. Sára ho pak tipuje – vždy řekne nějaké své číslo a Petr jí odpoví, jestli je jeho číslo menší nebo větší než Sářino.
Petra hra pomalu přestává bavit, jenomže Sára je k nezastavení a pořád ho přemlouvá. Tak si Petr řekl, že naprogramuje jednoduchý internetový server, který bude hru hrát za něj, a pak si půjde číst Průvodce labyrintem algoritmů.
Sára si se serverem může povídat protokolem HTTP. Pokaždé serveru pošle své
číslo jako součást URL. Server pak odpoví jediným řádkem textu: Pridej
(pokud je Petrovi číslo větší než Sářino), Uber (pokud je Petrovo číslo
větší), případně Trefa (pokud Sára číslo uhodla).
Sáru ovšem hádání po chvíli také přestalo bavit a chtěla se začíst do kuchařek KSP. Bylo jí líto nechat Petrův server nevyužívaný, tak se rozhodla, že napíše program, který bude hádat za ni. Vašim úkolem je jí s tím pomoct.
V odevzdávacím systému si necháte vygenerovat vstup. Na prvním řádku vstupu najdete
rozsah R – Petrův server si myslí nějaké celé číslo od 1 do R. Na druhém řádku se nachází
URL serveru. Když ho zadáte do webového prohlížeče a na konec připíšete „&q=číslo“, dozvíte se
odpověď na daný tip: jeden z řetězců Pridej, Uber, Trefa.
Píšete-li program v Pythonu, můžete se serverem komunikovat pomocí knihovny requests.
Dělá se to například takto:
http://ksp.mff.cuni.cz/viz/34-Z1-3-ukazka.py
V případě technických problémů při komunikaci se serverem se nebojte ozvat organizátorům o pomoc (podrobnosti na konci zadání).
Jako výstup pak v odevzdávacím systému odešlete jednořádkový soubor, ve kterém bude uhodnuté číslo.
34-Z1-4 Šíření zpráv (14 bodů)
Kevinovi se právě podařilo vyřešit všechny tři opendatovky v sérii! Orgové jsou z toho velice nadšení, a tak se informace o Kevinově úspěchu v orgtýmu rychle šíří.
Na začátku si toho všimla Kristýna. Ta se následně jala informovat Honzu, Kubu a nakonec i Davida. Honza to přeposlal Zuzce, ta zase zpátky Kubovi…
Mezitím Jirka a Jirka dosud nemají o Kevinovi ani ponětí. Jediné, o čem spolu momentálně diskutují, je včasná příprava další série.
Máte k dispozici záznam veškerých odeslaných zpráv na mailovém serveru, přes který si orgové dopisují.
Jeden řádek záznamu má formát <čas> <ID odesílatele> <ID adresáta>.
Celkem záznam obsahuje M řádků setřízených vzestupně podle času odeslání zprávy.
Můžete předpokládat, že časy jsou unikátní.
Samotné identifikátory (ID) lidí jsou pak celá čísla od 1 do N.
Na začátku ví o Kevinově úspěchu jenom člověk s ID 1. Každý člověk, který už ví, si informaci nenechá pro sebe. Pokud tedy někomu píše, určitě se ve zprávě zmíní i o Kevinovi. Opačně to platí podobně. Tedy člověk, který se o Kevinovi zatím nedozvěděl, o něm nemůže mluvit.
Vaším úkolem je zjistit, kteří lidé budou na konci (tj. po odeslání všech M zpráv) vědět o Kevinově velkolepém úspěchu. Jako výstup vypište setřízený seznam ID všech informovaných lidí.
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í.