Druhá série začátečnické kategorie dvacátého devátého ročníku KSP

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

• Termín série: 19. prosince 2016 v 8:00
• 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

• 29-Z2-1: Krocení zlé želvy
• 29-Z2-2: Sářina volba
• 29-Z2-3: Petr v říši divů
• 29-Z2-4: Zuzka: Cesta tam a zase zpátky
• 29-Z2-5: Dva roky bez prázdnin
• 29-Z2-6: Devět trpaslíků

29-Z2-1 Krocení zlé želvy (8 bodů)

Kevin a jeho kamarádi mají za sebou první nudné týdny školy a už zase vymýšlejí, co zajímavého by mohli podniknout. Před prázdninami dostal Kevin od rodičů želvu jménem Želva a tenkrát se ji rozhodl vycvičit. Tak proč dnes při dlouhém podzimním večeru v krocení nepokračovat?

Spolu se Sárou dávají Želvě pokyny „popojdi dopředu“, „otoč se na místě doprava“ a „otoč se na místě doleva“. Protože není Kevinův pokojíček moc velký, potřebují si radši předem rozmyslet, kde Želva po sérii pokynů vlastně skončí.

Želvičku na začátku položí do středu pokojíku na pomyslné souřadnice [0,0] natočenou severním směrem a zajímalo by je, kde skončí. Když vám Kevin a Sára postupně poví plánované příkazy, dokážete říct, kam se Želva dostane?

Tvar vstupu: Na prvním řádku od nich dostanete celkový počet pokynů, tedy jedno číslo. Na druhém řádku bude odpovídající počet znaků, kde > značí „otoč se doprava“, < znamená „otoč se doleva“ a A je „popojdi dopředu“.

Tvar výstupu: Od vás by potřebovali dostat dvě čísla (souřadnice) na jednom řádku oddělená mezerou. První říká, jak daleko je želva v pomyslném západně-východním směru, a to druhé odpovídá severo-jižnímu směru.

7
>A><AA>

3 0

Řešení

29-Z2-2 Sářina volba (10 bodů)

Když už Sáru přestalo krocení želvy Želvy bavit, začala přemýšlet nad plány na víkend. Uvažovala, že vyrazí s Petrem za dobrodružstvím. To se Kevinovi moc nezdálo a říkal, že by raději šel na výlet. Jak teď rozhodnout?

No jak jinak než si dát kámen-nůžky-papír. Oba se shodli, že rozhodnutí bude spravedlivější, když kámen-nůžky-papír zopakují několikrát za sebou. Plány na víkend rozhodne ten, který vyhraje vícekrát. Zjistíte, kdo to bude, jestliže víte, kolikrát celkem hráli a jak táhli?

Tvar vstupu: Na prvním řádku dostanete počet her, na druhém uvidíte, jaké tahy zvolila Sára, a na třetím jak volil Kevin (písmena K, N a P).

Tvar výstupu: Na jeden řádek vypište dvě čísla oddělená mezerou. První bude počet výher Sáry a to druhé udá, kolikrát zvítězil Kevin. V případě, že oba táhnou stejně, výhra se nepočítá ani jednomu.

4
KNPK
NPPP

2 1

Řešení

29-Z2-3 Petr v říši divů (10 bodů)

Kevin a Sára se i po úmorné sérii kámen-nůžky-papír nakonec rozhodli, že se prostě rozdělí. Sára s Petrem tedy vyrazili na procházku do blízkého lesa.

Ale co vypadalo jako obyčejný smrkový háj, se velmi rychle stalo neproniknutelným bludištěm. Jako by se najednou ocitli v nějaké pohádce. Petr a Sára z něj nemohou najít cestu ven. Petr začíná panikařit a tam Sára rychle přichází s plánem, jak zmapovat situaci.

Není náhoda, že lesy v pohádkách připomínají pravidelnou mřížku. Rozhodne se tedy, že zkusí zjistit počet pro ně dostupných políček. Dostupná políčka jsou taková, na která lze dojít z počátečního, pokud smíme dělat kroky jen vodorovně a svisle, ne šikmo. Když vám ukážeme mapu lesa, dokážete Sáře poradit?

Tvar vstupu: Na prvním řádku najdete šířku a výšku mapy, v tomto pořadí. Místo, kde s Petrem stojí, je označené P, volná políčka jsou . a neprostupná značíme #.

8 4
.###..##
..#.P..#
##...###
####....

0.9
13

Řešení

29-Z2-4 Zuzka: Cesta tam a zase zpátky (12 bodů)

Zatímco Petr a Sára bloudili v lese, Kevin vyrazil se Zuzkou na túru do hor. Rozhodli se, že budou velmi pečlivě zaznamenávat údaje o své cestě, protože nikdy nevíte, na co se to může hodit. Mají GPS, která každou sekundu zaznamenává jejich nadmořskou výšku.

Po pár kilometrech se už Zuzka cítí dost zničená a připadá si, jako by chodili pořád jen do kopce. Tvrdí, že už nevydrží jít do kopce ani minutu. Kevin jí to chce vymluvit, ale neobejde se bez pádných argumentů.

Chtěl by v záznamech najít co nejdelší úsek cesty, ve kterém šli maximálně minutu do kopce. Protože si ale Zuzka může vymyslet jakýkoliv jiný časový údaj než minutu, rád by to uměl spočítat pro zadané K. Pomůžete mu?

Dostanete čísla N a K, následované N záznamy nadmořské výšky. Najděte co nejdelší úsek, ve kterém šli Kevin se Zuzkou nejvýše K sekund do kopce a vypište, kolik sekund tento úsek trval.

9 2
1 2 4 3 1 -1 0 1 3

5

Hledaný nejdelší úsek začíná dvojkou a končí nulou. Úsek obsahuje šest záznamů, ale mezi těmito záznamy uplynulo pět sekund.

Řešení

29-Z2-5 Dva roky bez prázdnin (12 bodů)

Sára a Petr prohledávali les a najednou se před nimi zničeho nic objevil kocour Šklíba. Prý jim ukáže cestu, když mu pomohou vyřešit jeden problém.

Šklíba má starosti jako každý smrtelník, a tak ho mimo jiné trápí nekonečné množství spamů a řetězových e-mailů. Určitě to také znáte, jeden hrozí za nepřeposlání vynálezem zkázy, jiný slibuje každému, kdo jej nepřepošle alespoň dvaceti pohádkovým bytostem, strávit zbytek života dvacet tisíc mil pod mořem.

Poslední dobou se v říši divů rozmohl obzvláště otravný e-mail hrozící, že každý, kdo ho nepřepošle, bude dva roky bez prázdnin. Tohle bylo už i na Šklíbu moc, protože se rozšířil ještě více než ty předchozí. Po Petrovi a Sáře chce vypátrat, kdo je autorem tohoto spamu.

Původce e-mail rozeslal K bytostem. Každá z nich jej buď smazala, nebo přeposlala zase K lidem. Dobrou zprávou je, že nikdo nedostal e-mail dvakrát. Šklíba má k dispozici informace, mezi kterými dvojicemi putoval, ale nedokázal už zjistit, kterým směrem (tzn. kdo jej poslal komu). Dokážete vymyslet způsob jak odhalit, kdo začal tento řetězový e-mail a pomoci tak Sáře s Petrem?

Řešení

29-Z2-6 Devět trpaslíků (14 bodů)

Zuzka s Kevinem pokračovali v cestě, když se najednou začalo až překvapivě rychle stmívat. Rozhodli se nic neriskovat a vrátit se zpátky, ale kudy? Tam, kde se v mapce nachází turistická stezka, je ve skutečnosti hustý neproniknutelný les.

Chvíli bloudili sem a tam, tam a sem, a když už jim začínalo být úzko, potkali Sáru s Petrem. Ty poslal Šklíba hledat pomoc k devíti trpaslíkům. Kevin se Zuzkou se k nim přidali a po chvíli Sněhurku i se všemi devíti trpaslíky našli.

Ti už pro naše čtyři kamarády měli připravený další úkol. Dostanou řadu N čísel v jistém pořadí a čas na přípravu. Pak jim budou trpaslíci klást spoustu dotazů typu: „Jaký je součet čísel mezi a-tým a b-tým číslem?“ Poradíte jim, jak se co nejlépe připravit, aby takový dotaz mohli zodpovědět co nejrychleji?

Sněhurka chce navíc vědět, kolik času je na přípravu potřeba, co si budou muset pamatovat navíc a samozřejmě i čas potřebný na zodpovězení jednoho dotazu.

Pokud to potřebujete, předpokládejte, že dotazů bude řádově N.

Řešení