Pátá série začátečnické kategorie třicátého páté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 35. 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ích čtyř sérií.

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 úloha35-Z5-1 Jen tak mimochodem (8 bodů)

Kevin jednou za čas dochází na přednášky na jednu nejmenovanou universitu. Nejvíce ho zaujaly přednášky profesora Hrošíčka, který je proslulý nejen tím, že si nikdo ze studentů není jistý, co že to vlastně přednáší (byť se všichni shodnou na tom, že to je velice zajímavé), ale také tím, že neustále, mnohdy i vícenásobně, odbočuje od tématu.

Kevin si samozřejmě poctivě píše zápisky, ale možná až moc poctivě – jeho zápisky obsahují také všechny profesorovy odbočky. Pomozte Kevinovi proškrtat jeho zápisky tak, aby obsahovaly pouze obsah přednášky bez odboček. Odbočky se poznají tak, že začínají nějakou odbočovací frází (např. „To mi připomíná …“) a končí nějakou vracecí frází (např. „ … ale zpět k tématu.“), ale pozor, taková odbočka může mít další odbočku vnořenou v sobě!

Slibujeme, že vstupní text má jednoznačné řešení a nevyskytují se v něm okrajové případy. Například nikdy se nestane, že nějaká odbočovací fráze je zároveň i vracecí fráze, nebo že se dvě odbočovací nebo vracecí fráze v textu překrývají.

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 O a V na prvním řádku, potom následuje nejdříve O odbočovacích a poté V vracecích frází, každá tvořená nejdříve jedním řádkem s číslem C a poté druhým řádkem s C znaky tvořícími samotnou frázi. Na předposledním řádku je číslo P a na posledním P znaků reprezentujících samotný obsah zápisků. Všechna vstupní data jsou v ASCII a jedná se o slušně vychovaný text, který neobsahuje žádné divoké netisknutelné znaky. Na počtu mezer nezáleží (více mezer se počítá jako jedna) a odbočky nemusí být od zbytku textu odděleny mezerou.

Formát výstupu: Jeden řádek s celým textem zápisků bez odboček.

Ukázkový vstup: 
1 1
1
(
1
)
30
Ahoj (neco (haha) bagr) svete!
Ukázkový výstup: 
Ahoj svete!

Řešení

Praktická opendata úloha35-Z5-2 Zlaté stránky (12 bodů)

Těžbou zlata v minulé sérii si Kevin vydělal slušnou sumičku. Jenže víte, jak to chodí: ceny zboží (a zejména potravin) strmě rostou, a tak hrozí, že si brzy za plody své dřiny nedá ani pořádný oběd. Výdělek bude třeba zhodnocovat, aby rostl alespoň tak rychle jako ostatní ceny.

Kevin jedná v panice a rychle zakládá startup na výrobu rovných křivítek. Průzkum trhu by mu nejspíš napověděl, že takový výrobek je neprodejný, ale teď už je pozdě. Vrchní výkonná ředitelka (opět Zuzka) však přichází s mistrným plánem: „Přejmenujeme naši společnost tak, aby v rejstříku padla hned vedle slavného výrobce křivých křivítek – Hipporty. Zmatení zákazníci si tak koupí náš produkt a vyděláme.“

Kde v tomto brilantním plánu vězí háček? Jistě, v byrokracii. Soudní úředníci, kteří mají rejstříky na starosti, lepí písmenka ze samolepek. Jejich dodávky ale poslední dobou váznou, a tak je výběr velmi omezený. Poraďte Zuzce, jak společnost přejmenovat, aby na soudu šla zapsat a přitom padla k Hipportě co možná nejblíže.

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 je 26 čísel oddělených mezerou, každé značí počet dostupných písmen popořadě dle abecedy. Uvažujeme malou anglickou abecedu, tedy a-z bez ch.

Na druhém řádku je číslo N a na třetím N-písmenný oficiální název společnosti Hipporta, opět složený pouze z malé anglické abecedy.

Formát výstupu: Na výstupu uveďte jediný řádek s názvem Kevinovy společnosti. Ten musí mít stejnou délku jako oficiální název Hipporty, používat pouze dostupná písmena v dostupných počtech a zároveň být abecedně co možná nejblíže Hipportě. Pokud by si někdo za stejných omezení taktéž registroval název délky N, nesmí se mu podařit dostat abecedně mezi Kevina a Hipportu. Pokud je možných odpovědí více, uveďte libovolnou z nich.

Ukázkový vstup: 
1 1 1 1 1 0 0 2 2 0 0 3 1 2 6 3 0 2 3 1 1 0 2 0 2 3
23
hrosispolecnosthipporta
Ukázkový výstup: 
hrosispolecnosthipporua

Řešení

Praktická opendata úloha35-Z5-3 Karneval (14 bodů)

„Nádhera,“ říkají si Kevin se Zuzkou při pohledu na nový název jejich startupu na rovná křivítka. „Už se těším, až bude reklama na Hipqabff viset na všech billboardech,“ lebedí si Kevin. Teď už jen stačí na ten úřad zajít a firmu zapsat. Jako na potvoru je však dnes ve městě karneval, a jak všichni víme z akčních filmů, karneval tvoří neprostupnou překážku. Do zítřka Kevin se Zuzkou taky čekat nemohou, ještě by jim jejich název firmy někdo vyfoukl před nosem! Pomozte Kevinovi a Zuzce dorazit na úřad ještě dnes, přestože cestu komplikuje probíhající karneval.

Město je dvourozměrná mřížka. Některá políčka jsou průchozí (ulice, parky, atd.), jiná jsou zastavěna neprostupnými budovami. Kevin se Zuzkou se nacházejí ve své nové kanceláři (u Kevina doma v garáži) a chtějí dojít na úřad. Na náměstí však začal karnevalový průvod, který postupuje severním směrem (neboli nahoru) stejnou rychlostí jako chodí Kevin se Zuzkou. Protože na karneval přišlo opravdu hodně lidí, tak je to takový nekonečný had. Kde se jednou octne „předek“ karnevalu, tam už nikdy Kevin se Zuzkou neprojdou, protože tudy až do večera bude proudit průvod.

Kevin se Zuzkou chodí vždy o jedno políčko nahoru, dolů, doleva nebo doprava (nemohou chodit diagonálně). Poté, co se pohnou, pohne se i karneval – předek karnevalového průvodu se pohybuje určitým směrem (ze začátku směrem nahoru), kterým udělá jeden „krok“ a na jeho předchozím místě bude už na věky věků procházet karnevalový průvod, který je pro naše kamarády neprostupný. Pokud předek karnevalu nemůže jít dopředu (protože narazil na budovu nebo okraj města), otočí se doprava a ihned udělá krok tímto směrem. Pokud je i vpravo budova, otočí se opět doprava a vrací se kudy přišel. Karnevalový průvod umí procházet sám sebou v libovolném směru.

Vaším úkolem je najít cestu, kudy se Kevin se Zuzkou dostanou z Kevinova domu na úřad s tím, že neprojdou postupujícím karnevalovým průvodem.

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 2 čísla: N a M udávající výšku a šířku mřížky.

Na následujících N řádcích bude vždy M znaků, které udávají, co se na dané pozici nachází.

Formát výstupu: Zajímá nás, jaké přesně kroky mají Kevin se Zuzkou dělat, aby došli na úřad. Vypište tedy na jeden řádek postupně za každý krok jedno písmeno: N pro nahoru, D pro dolů, L pro doleva a P pro doprava.

(Nemusíte najít přímo nejkratší řešení, ale velmi, velmi dlouhá řešení nepůjdou nahrát do odevzdávátka.)

Ukázkový vstup: 
5 11
__DXXXXXU__
_X____XXXX_
_P_______X_
________X__
XXXXX_____X
Ukázkový výstup: 
LLDDDPPPPPPPDPPNPNNNLL

Řešení

Teoretická úloha35-Z5-4 Protipříklad (10 bodů)

Kamarádi jedou na výlet a baví se čtením nápisů na billboardech. Kevin hlásí, že vidí MADLO. Petr objevil nápis LAMA a Sára se chechtá, že celá reklama je jenom KLAM. Brzy přijdou na to, že každý viděl svým okénkem svůj kousek velkého nápisu KLAMADLO.

Teď vymýšlejí další slova a zkoušejí najít co nejkratší společný nadřetězec, tedy řetězec, ve kterém se vyskytují všechna zadaná slova jako souvislé podřetězce.

Kevin navrhuje algoritmus: podívá se, která dvě slova mají co nejdelší překryv, a ta slepí dohromady. Takhle pokračuje, dokud nevznikne jediné slovo. Takže pro LAMA, KLAM a MADLO by nejdříve slepil KLAM a LAMA do KLAMA (protože tato dvě slova mají tříznakový překryv, zatímco KLAM a MADLO jenom jednoznakový, LAMA a MADLO dvojznakový a lepení slov v opačném pořadí nedává vůbec žádný překryv). V druhém kroku by slepil jedinou zbývající dvojici KLAMA a MADLO, čímž by dostal KLAMADLO.

Sára se Kevinovi směje, protože tohle je přeci typický příklad hladového algoritmu a ty skoro nikdy nefungují. Pomozte Sáře najít protipříklad: množinu slov, pro kterou Kevinův algoritmus najde nadřetězec, který je zbytečně dlouhý. Tedy existuje nějaký jiný nadřetězec, který je kratší.

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í