Třetí série začátečnické kategorie třicátého druhého ročníku KSP

Celý leták, který posíláme také papírově, v PDF.

Vítáme vás u třetí série začátečnické kategorie KSP. Tato série je poslední před letošním jarním soustředěním, může vám tedy pomoci ovlivnit, jestli budete vybráni.

Kdo může řešit? Každý středoškolák nebo základoškolák, a to i ten, který neřešil série minulé. Pokud máte jakýkoli dotaz, zeptejte se našeho webu nebo přímo nás. Kontakty najdete v patičce na konci letáku.

Přejeme hodně zábavy při řešení dalších úloh!

• Termín série: 6. dubna v 8:00, praktické úlohy za třetinu bodů až do 13. 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

• 32-Z3-1: Tiskařský stroj
• 32-Z3-2: Sářina omalovánka
• 32-Z3-3: Akční ceny
• 32-Z3-4: Dálnice
• 32-Z3-5: Čtyři kamarádi
• 32-Z3-6: Světelný hlavolam

32-Z3-1 Tiskařský stroj (8 bodů)

Zima už dávno měla být v plném proudu, ale sníh pořád nikde. Venku je teplo jako na jaře a zdá se, že příroda letos zimu úplně vynechala. Když si Kevin nemůže užívat zimní prázdniny, musí si najít jinou zábavu. Napadlo ho zabít nudu zkoumáním tiskařských strojů. To by bylo něco, vytisknout si vlastní knihu stejně jako Gutenberg v 15. století! Určitě ale trvá strašně dlouho poskládat každou stránku z jednotlivých písmenek. Petr se proto rozhodl tisk vylepšit: místo jednotlivých písmenek vyrobí odlitky dvojic písmen a bude text skládat z nich.

Kevin si ale není úplně jistý, že tento revoluční způsob bude rychlejší. Chce proto nejdřív sestavit prototyp jen s některými dvojicemi písmen – těmi nejčastějšími. Poradíte mu, které dvojice to jsou?

Slibujeme, že v textu se budou vyskytovat pouze malá písmenka anglické abecedy a mezery. Dvojice písmen jsou dvě písmena v jednom slově bezprostředně za sebou. Například v textu skrz krk se mimo jiné nachází dvakrát dvojice kr, jednou dvojice rk a ani jednou dvojice zk.

Tvar vstupu: Na prvním řádku naleznete číslo k a na druhém řádku bude text knihy. Vaším úkolem je nalézt v textu k nejčastějších dvojic písmen.

Tvar výstupu: Vypište k nejčastějších dvojic písmen v daném textu, každou na jeden řádek. Na pořadí vypisování nezáleží. Pokud je dvojic se stejným počtem výskytů více, vypište libovolné z nich.

2
bylo nebylo

lo
yl

Další z možných řešení je třeba by, yl nebo yl, lo.

Řešení

32-Z3-2 Sářina omalovánka (10 bodů)

Sára si čas krátí kreslením. Když už jí docházely nápady, co může malovat, vzala si čtverečkovaný papír a začala vybarvovat jednotlivé čtverečky. Nejprve vybarvila několik náhodných čtverečků různými barvami. Tyto čtverečky nazvala počátečními. Pak Sára začala postupně vybarvovat ostatní čtverečky: vždy zjistila, který počáteční čtvereček je k danému čtverečku nejblíž, a tou barvou ho vybarvila. Pokud má nějaký čtvereček dva nejbližší počáteční čtverečky různé barvy, nechá ho Sára nevybarvený.

Vzdálenost čtverečků Sára počítá podle manhattanské metriky: vzdálenost mezi čtverečky A a B je rovna počtu kroků nahoru nebo dolů plus kroků doleva nebo doprava, které musíme udělat ze čtverečku A, abychom se dostali na čtvereček B.

Otázka zní: Jak bude vypadat výsledný obrázek?

Tvar vstupu: Na prvním řádku dostanete čísla R a S, které značí počet řádků a sloupců obrázku. Dále bude následovat obrázek tvořený S znaky na každém z R řádků. V obrázku tečka značí prázdné políčko a písmenka anglické abecedy reprezentují počáteční políčka.

Tvar výstupu: Vypište výsledný obrázek. Každé políčko reprezentujte příslušným znakem anglické abecedy, je-li vybarvené, nebo tečkou, pokud vybarvené není.

8 6
....t.
......
..T...
......
......
.....b
......
.b....

...ttt
TTT.tt
TTTT..
TTTT.b
..T.bb
bb.bbb
bbbbbb
bbbbbb

Řešení

32-Z3-3 Akční ceny (10 bodů)

Petr tráví zimní prázdniny brigádou v jednom obchodě. Pozoruje, kolik zákazníků který den přijde. Zrovna dneska tu je zákazníků celkem málo. „Na konci týdne by se to ale mělo zlepšit,“ pomyslel si Petr, „a za dva týdny tu zase máme narváno.“ Vypadá to, že zákazníci chodí ve vlnách, protože stejný výkyv už tu Petr jednou viděl.

Jak jinak tuhle domněnku ověřit než porovnat pravdivá data? Petr má záznamy o počtu zákazníků za tento kvartál a za ten minulý. Chce najít nejdelší úsek, ve kterém byly počty zákazníků v prvním i druhém kvartálu stejné.

Tvar vstupu: Na prvním řádku najdete počet dní n, pro které máme záznamy. Na druhém a třetím řádku najdete vždy n čísel oddělených mezerou, neboli dvě posloupnosti počtů zákazníků.

Tvar výstupu: Na první řádek napište délku nejdelšího společného úseku obou posloupností (nejdelší společný úsek nemusí začínat na stejném indexu). Na druhý řádek úsek vypište, čísla oddělujte mezerami. Pokud existuje více různých nejdelších úseků, vypište kterýkoliv z nich.

6
11 5 10 8 6 7
1 7 5 10 8 9

3
5 10 8

Řešení

32-Z3-4 Dálnice (12 bodů)

V Kevinově městě má vyrůst nová dálnice. Už se o tom mluví pěkně dlouho. Když šel Kevin se svou mladší sestrou Zuzkou na procházku, schválně se vydali směrem k místu plánované stavby. Jestlipak už začali dálnici stavět? To by si mohli prohlédnout bagry a další těžké stroje, bylo by to určitě moc zajímavé!

Ale ouha, stavět ještě nezačali. A co hůř, dokonce ještě ani není naplánované, kudy přesně dálnice povede. Tedy, jen přibližně. Kevin pohledem do katastru nemovitostí zjistil, že stavební firma skoupila pozemky tvořící koridor, který vede přes celý plánek obce zeshora až dolů. To je ale široký koridor, pomyslel si Kevin. Kolikaproudá dálnice to asi bude?

Pomozte Kevinovi zjistit, kolik nejvíce pruhů může dálnice v daném koridoru mít. Dostanete na vstupu ve čtverečkové síti vyznačený koridor. Koridor je široký pruh vedoucí odshora až dolů a jehož boční strany mohou být různě „zubaté“. Neobsahuje tedy žádné ostrůvky, ani se nikde nedělí. Každý jízdní pruh má šířku jeden čtvereček, může libovolně zatáčet do čtyř směrů a musí se po něm dát dostat od horní strany mřížky až k té spodní. Pruhy se mohou rozbíhat, ale nesmí se překrývat s jinými pruhy.

Tvar vstupu: Na prvním řádku budou dvě čísla R a S, udávající počet řádků a sloupců. Na dalších R řádcích bude pokaždé S znaků. Mohou to být tečky a křížky. Tečka (.) znamená, že toto políčko leží v koridoru a může tudy vést dálnice. Křížek (#) znamená, že toto políčko stavební firma nekoupila, takže dálnice přes něj vést nemůže.

Tvar výstupu: Odpovězte jedním číslem, kolik pruhů může dálnice maximálně mít.

6 7
##...##
#.....#
#....##
###...#
#.....#
##....#

2

Pruhy mohou vypadat takto:

##1.2##
#.1.2.#
#.112##
###12.#
#.112.#
##1.2.#

Řešení

32-Z3-5 Čtyři kamarádi (12 bodů)

Kevin, Sára a Petr se potkali se svojí kamarádkou Helenou, kterou dlouho neviděli. Všichni čtyři spolu chodí celý den po městě, ale večer se musí rozloučit – do půlnoci musí být všichni doma. Rádi by ale vymysleli, kde se rozloučit tak, aby to bylo co nejpozději a přesto se každý dostal domů včas.

Město si můžeme představit jako čtverečkovou síť, ve které se dá chodit nahoru, dolů, doleva a doprava a každý takový pohyb trvá jednu jednotku času. Na některá políčka se nedá vstoupit a je potřeba je obejít – ulice ve městě jsou občas jako bludiště. Každý z kamarádů bydlí v jednom z rohů této čtverečkové sítě. Vaším úkolem je najít takové políčko, ze kterého se i kamarád s nejvzdálenějším domem dostane domů co nejrychleji.

Příklad:

        K#......S
        .#.#..##.
        ...#.#...
        ..#Z.....
        ..#.#.#..
        ....#..#.
        .#.#..#..
        ..#....#.
        P...##.#H

Když se v tomto příkladě kamarádi rozloučí na políčku označeném Z, Kevinovi a Heleně bude cesta domů trvat 10 jednotek času. Kdyby se rozloučili kdekoliv jinde, někomu z kamarádů by cesta trvala déle a museli by se tedy rozdělit dřív, aby byli všichni doma včas.

Řešení

32-Z3-6 Světelný hlavolam (14 bodů)

Zuzka má doma zajímavý hlavolam. Je to taková krabička, na které je n tlačítek. Na začátku některá tlačítka svítí a některá ne. Na zmáčknutí jednoho tlačítka hlavolam nereaguje. Když ale Zuzka zmáčkne libovolná tři tlačítka najednou, každé z těchto tří tlačítek změní svůj stav: pokud předtím svítilo, tak zhasne, a pokud bylo zhasnuté, tak se rozsvítí. Cílem hlavolamu je rozsvítit všechna tlačítka.

Zjistěte, pro která n a pro které počáteční kombinace rozsvícených tlačítek jde hlavolam vyřešit, a popište jak.

Příklad: Pro počáteční stav 01011010 (1=svítí, 0=nesvítí) zmáčkneme nejprve první, druhé a třetí tlačítko, čímž přejdeme do stavu 10111010. Poté zmáčkneme zbyla tři zhasnutá tlačítka.

Jiný příklad: Z počátečního stavu 010 nelze všechna tlačítka rozsvítit. Zmáčknutím trojice se totiž dá dostat pouze do stavu 101 a z něj zase jen zpět do 010.

Řešení