Druhá 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 druhé série 34. 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 12. prosince ve 32:00 (tedy další ráno v 8:00), praktické úlohy za třetinu bodů až do 19. 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
- 34-Z2-1: Dýňová polévka
- 34-Z2-2: Podivná brigáda
- 34-Z2-3: Skládání krabic
- 34-Z2-4: Dělení království
34-Z2-1 Dýňová polévka (7 bodů)
Podzim je nádherné roční období. Příroda nabízí okouzlující scenérii. Všude je barevné listí, ořechy a děti pouštějící draky. A taky studený vítr. A ze zimy hlad.
Tyto myšlenky se honily Kevinovi hlavou, když tu ucítil lahodnou vůni dýňové polévky. „To je ono, polévka zasytí i zahřeje,“ pomyslel si a rozeběhl se ke stánku. Jenže zrovna před minutou zavřeli. „Nevadí, za 100 metrů je další,“ říká si utíkaje k němu. Jenže ten zas otevírá až za 3 hodiny. Kevin už hlady skoro šilhá. Poradíte mu, kolik polévek cestou domů stihne?
Kevin jde domů ulicí plnou pravidelně rozmístěných stánků. Kdykoli potká otevřený, dá si u něj polévku, což mu zabere 10 sekund. Poté opět vyrazí. Zavřené stánky po cestě zcela ignoruje.
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: Na prvním řádku jsou celá čísla D, S a N oddělená mezerou. Na následujících N řádcích jsou otevírací doby stánků zapsané jako A B, kdy A je počet sekund od začátku dne, kdy stánek otevře, a B kdy zavře. Zákazníky obsluhují i v krajních časech tohoto intervalu.
Na počátku stojí Kevin u prvního stánku S sekund od začátku dne. Chůze mezi sousedními stánky Kevinovi trvá D sekund.
Dny na Kevinově planetě bývají velmi dlouhé, speciálně tedy nespoléhejte, že časové údaje budou nejvýše 86400 – slibujeme pouze, že se vejdou do 32b čísla (nedůležité, programujete-li v Pythonu).
Výstup: Na první řádek vypište počet stánků, u nichž si Kevin dal polévku.
10 5 6 2 7 10 15 37 40 44 100 50 60 1 100
3
34-Z2-2 Podivná brigáda (11 bodů)
Kevin a Sára se rozhodli na základě inzerátu v novinách zkusit brigádu v cestovní kanceláři. Mysleli si, že náplní jejich práce bude cestování, ale nakonec se z toho vyklubala otravná kancelářská práce.
Každý den na ně čekala společná hromada dokumentů, které bylo potřeba zpracovat. Dokumenty nejsou stejné – každý z nich potřebuje jiný čas na zpracování.
Kevin i Sára z této hromady postupně odebírají dokumenty a zpracovávají je každý sám. Chtějí to mít co nejdříve za sebou, takže kdykoliv jeden dokument zpracují, vezmou si hned další v pořadí. V případě, že oba zpracují dokument ve stejnou chvíli, z hromádky si dokument vezme první Kevin.
Domů můžou odejít až tehdy, když jsou všechny dokumenty zpracované.
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 dokumentů na hromádce. Na následujících N řádcích jsou časy v celých minutách potřebné pro zpracování daného dokumentu směrem od horního z hromádky ke spodnímu.
Výstup: Vypište, po kolika minutách od zahájení práce bude mít Kevin se Sárou hotovo.
8 1 2 3 1 1 2 2 3
9
34-Z2-3 Skládání krabic (13 bodů)
Petr se rozhodl, že letos nebude řešit vánoční dárky na poslední chvíli. Sice zatím nevymyslel, co svým kamarádům koupí, ale už teď ví jistě, že bude potřebovat spoustu krabic na zabalení dárků. Proto se rozhodl, že půjde do obchodu a sežene tam co nejvíc krabic různých velikostí.
V obchodě mají krabice na jedoucím pásu, všechny mají tvar krychle. Petr je chce skládat do sebe tak, aby nakonec nesl jen jednu krabici, ve které budou uložené ostatní. Krabici může vzít z pásu, jen pokud má ostře větší objem než ta, kterou právě drží (pokud ještě žádnou nedrží, může vzít libovolnou). Krabici, co drží, vloží do nové, a pak vybírá zase větší krabici, do které by mohl aktuální krabici vložit.
Petr by potřeboval sehnat co nejvíc krabic. Vaším úkolem je zjistit, jaký je největší počet krabic, které si Petr může odnést domů.
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: Na prvním řádku dostanete číslo N udávající celkový počet krabic na pásu. Následuje N řádků s jedním číslem udávajícím délku hrany krabice. Krabice jsou krychlové, tudíž mají všechny hrany stejně dlouhé.
Výstup: Vypište číslo udávající maximální počet krabic, které si může Petr odnést domů.
10 4 1 3 8 8 12 6 25 14 16
6
34-Z2-4 Dělení království (13 bodů)
Kdysi dávno a kdesi daleko byla dvě hroší království. Nazývejme je podle jejich hroších králů Arocha a Brocha. Hroší králové vyhráli válku se sousedním královstvím Pelikánů.
Na obsazeném území hroši našli n různých měst a ta byla spojena m různými cestami. Nově získaná města si chtěli králové mezi sebe rozdělit, ale neměli to tak jednoduché.
Aroch a Broch chtěli zlepšit vztahy mezi svými královstvími, a tak se dohodli, že každé město z jednoho království bude obchodovat jen s městy z toho druhého království. Králové by si tedy rádi nově získaná města rozdělili tak, aby spolu nikdy nesousedila dvě města z téhož království.
Jakkoli se však králové snažili, města se jim nedařilo rozdělit. Dokázali byste to vy?
Na vstupu dostanete seznam měst a seznam dvojic měst, mezi kterými vede cesta. Určete, jestli lze města rozdělit mezi království.
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í.