Čtvrtá 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 čtvrté 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 30. března ve 32:00 (tedy další ráno v 8:00), praktické úlohy za třetinu bodů až do 6. dubna
- 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-Z4-1 Kevinova dieta (8 bodů)
Kevin se jednoho dne rozhodl, že vyrazí na výlet. Sbalil svačinu, nazul pohorky a vyrazil. Když už nějakou dobu chodil, rozhodl se, že si dá čokoládu, kterou si vzal s sebou. Jak známo, Kevin má rád čtverce. A čím větší, tím lepší, což aplikuje i na jedení čokolády. Vždycky se tedy snaží jako první dílek sníst co největší čtverec. Když vytáhl tu dnešní z batohu, zjistil, že se mu po cestě rozlámala. Aspoň si už nebude muset s dělením lámat hlavu. Ale který dílek má sníst jako první?
Čokoládu si můžete představit jako tabulku s R řádky a S sloupci. Dále víte, na jakých místech se čokoláda přelomila. Každý zlom nastal mezi dvěma sousedními řádky nebo sloupečky, vždy po celé délce čokolády. Zajímá nás, jaký největší nepolámaný čtvercový kousek lze z čokolády vybrat.
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 jsou dvě přirozená čísla R a S – počet řádků a sloupců tabulky. Na druhém řádku jsou dvě přirozená čísla H a V – počet horizontálních a vertikálních zlomů. Na dalším řádku dostanete H přirozených čísel hi oddělených mezerou, kde i-té z nich značí, že došlo ke zlomení čokolády mezi řádky hi a hi+1. Na dalším řádku dostanete obdobně V čísel vi, z nichž i-té značí, že se čokoláda rozlomila mezi sloupečky vi a vi+1. Řádky i sloupce číslujeme od jedné. Slibujeme, že nějaký čtvercový kousek bude vždy existovat.
Formát výstupu: Na výstup vypište délku strany největšího celistvého čtverce, který lze z rozlámané čokolády vybrat.
6 7 3 3 1 2 5 2 3 6
3
37-Z4-2 Poker (10 bodů)
Kevinovi kamarádi hráli o přestávce mezi vyučováním poker. Kevin se chtěl přidat, ale vůbec neznal pravidla. Rozhodl se tedy, že bude zatím pozorovat, jak ostatní hrají. Podle toho, kdo vyhraje, se časem naučí poznat, která ruka karet je silnější.
Proběhlo několik her a Kevin je stále ztracen. Pomozte mu tím, že za něj seřadíte všechny ruky od nejsilnější po nejslabší.
Školní poker probíhá tímto způsobem: Každý hráč dostane své dvě karty. Následně se na stůl vyloží tři společné karty, které doplní karty jednotlivých hráčů. Tím získá každý hráč ruku sestávající z pěti karet.
Ruky se následně porovnají podle standardních pravidel pokeru. Zde nabízíme jejich souhrn.
Ruky se rozřadí podle výherních kombinací, které určí primární pořadí.
V případě rovnosti se porovnávají hodnoty karet, kde nejsilnější je eso (A),
následuje král (K), dáma (Q), kluk (J), 10 (T) a poté čísla 9 až 2.
Výherní kombinace od nejsilnější po nejslabší jsou:
- Straight flush, pět karet stejné barvy jdoucí po sobě.
V případě rovnosti rozhoduje hodnota nejvyšší karty.
Eso může být na začátku (
A2345, nejslabší z postupek) nebo na konci (TJQKA, nejsilnější z postupek). - Four of a kind, čtveřice karet stejné hodnoty. Rozhoduje hodnota karet ve čtveřici, případně pak hodnota páté karty.
- Full house, trojice karet stejné hodnoty a dvojice karet stejné hodnoty. Rozhoduje hodnota trojice, případně pak hodnota dvojice.
- Flush, pět karet stejné barvy. Rozhodují hodnoty karet seřazené od nejvyšší.
- Straight, pět karet jdoucích po sobě. Rozhoduje se stejně jako u straight flush.
- Three of a kind, trojice karet stejné hodnoty. Rozhoduje hodnota trojice, případně pak hodnoty dalších dvou karet seřazené od nejvyšší.
- Two pairs, dvě dvojice karet stejné hodnoty. Rozhoduje hodnota vyšší dvojice, případně pak hodnota nižší dvojice a nakonec hodnota poslední karty.
- One pair, dvojice karet stejné hodnoty. Rozhoduje hodnota dvojice, případně pak hodnoty dalších tří karet seřazené od nejvyšší.
- High card je poslední výherní kombinace, pokud žádná z výše uvedených neplatí. Rozhodují hodnoty karet seřazené od nejvyšší.
Ve všech případech se barvou karty myslí piky, srdce, káry nebo kříže (nikoli červená nebo černá).
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:
Karty popisujeme dvojicí znaků, kde první znak značí hodnotu (AKQJT98765432),
druhý znak značí barvu (shdc, z angličtiny).
Na prvním řádku dostanete počet hráčů N. Na druhém řádku jsou mezerou oddělené popisy tří karet na stole. Následuje N řádků, kde každý popisuje jednoho hráče: jméno bez diakritiky a dvě karty, které dostal.
Formát výstupu: Vypište jména hráčů seřazené podle síly jejich ruky, od nejsilnější po nejslabší. Slibujeme, že žádné dvě ruky nemají stejnou sílu (to by mohlo nastat, kdyby se lišily jen barvami karet).
Lehčí varianta (za 4 body): V prvních dvou vstupech mohou nastat pouze nejslabší čtyři výherní kombinace,
tedy three of a kind, two pairs, one pair a high card.
10 8d Jd 9d Zita 8c 8s Lubos 4d As Oliver 9c 2d Ursula 7s Ts Jiri Th Qc Vaclav Td Qd Silvie Td 2d Beata 8h Kh Tatana Jh 9c Borivoj 4d 5d
Vaclav Silvie Borivoj Jiri Ursula Zita Tatana Oliver Beata Lubos
Václav má straight flush.
Silvie a Bořivoj mají flush; u Silvie jsou hodnoty seřazené JT982, u Bořivoje J9854.
Jiří a Uršula mají straight; Jiří má postupku zakončenou královnou, Uršula klukem.
Zita má jako jediná three of a kind.
Taťána má jako jediná two pairs.
Oliver a Beáta mají one pair; Beáta má sice krále, ale rozhoduje hodnota páru a ten má vyšší Oliver.
Luboš žádnou výherní kombinaci nemá.
37-Z4-3 Turistka na blátě (12 bodů)
Přichází jaro, sníh začíná tát a všechno se mění v bláto. Kevin se rozhodl, že půjde na procházku do hor, ale protože mu ve městě bylo horko, zapomněl si vzít pořádné boty a má jen sandály. V batohu mu zbylo K náhradních ponožek, které vyhrál v pokeru. Kevin si také přinesl drona, protože chtěl natočit krásné záběry hor. Dron mu teď ale poslouží k jinému účelu. Kevin si s jeho pomocí umí udělat mapu hor a lokalizovat, kde se nachází bláto.
Pomůžete Kevinovi najít cestu v blátivých horách?
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.
Kevin potřebuje projít ze startu v údolí U na vrchol hory V, přičemž může projít přes políčko s blátem nejvýše K-krát. Dron umí Kevinovi vytisknout mapu o velikosti R ×S pixelů, kde každý pixel představuje políčko. Na každém políčku je buď suchá země, nebo bláto. Kevin se může pohybovat po suché zemi a může se posunout pouze na sousední políčka (tedy východ, západ, sever, jih). Protože Kevin má jen sandály, musí využít jedny ponožky z batohu za každé políčko s blátem, které projde.
Formát vstupu:
Na prvním řádku jsou tři čísla R, S a K, které reprezentují rozměry mapy a počet ponožek, které Kevin má
(jeho batoh je velký). Na dalších R řádcích je S znaků, které reprezentují mapu. Znak Z značí suchou
zemi a znak B značí bláto. Někde na mapě je také políčko startu z údolí U a vrcholu hory V.
Formát výstupu:
Na prvním řádku vypište délku vaší cesty D.
Na dalších D řádcích vypište cestu, kterou Kevin šel.
Cestu reprezentujte znaky V (východ), Z (západ), S (sever) a J (jih).
Zaručujeme, že z U do V vždy existuje cesta, kterou se Kevin dostane na vrchol hory a Kevin má dostatek ponožek na to aby to zvládl.
Poznámka: Kevin nemusí najít nejkratší cestu, ale jen cestu která ho dovede na vrchol hory.
4 10 2 BZBZUBZZZB BBZBZZBZBB BBVBBZZZZB BZZBZBZZBB
4 Z J Z J
37-Z4-4 Velikonoční zajíčci (14 bodů)
Blíží se Velikonoce a Kevin se vydal hledat proutky na pomlázku do nedalekého lesa. Koho ale nepotkal – velkou skupinu velikonočních zajíčků, hádajících se o svá vajíčka.
Zající se dělí do dvou skupin. Jedni mají vajíčka rádi malovaná a druzí čistá. Každý zajíc má svou preferenci. Zajíci jsou velmi mírumilovná stvoření, ale jak jde o vejce, tak jdou všechny žerty stranou. V takovém případě se hádají tak nahlas, že to slyší až v Hroším Týnci. Jak Kevin procházel, tak slyšel vždy dva zajíce se hádat. Pokud se dva zajíci hádají, tak jsou zcela určitě v opačných skupinách. Kevinovi se ale něco na tom, kdo se spolu hádá, nezdálo. Pomozte mu ověřít, jestli to, co slyšel, dávalo smysl.
Na vstupu dostanete seznam dvojic králíků, které Kevin zaslechl se mezi sebou hádát. Určete, jestli je možné je rozdělit do dvou skupin tak, aby se vždy hádali dva z různých skupin.
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í.