Čtvrtá série začátečnické kategorie třicátého prvního ročníku KSP

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

• Termín série: 10. června 2019 (praktické úlohy za třetinu bodů až do 17. června 2019)
• 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

• 31-Z4-1: Nejosamělejší kamarád
• 31-Z4-2: Závažíčka na druhou
• 31-Z4-3: Probíhání bludištěm
• 31-Z4-4: Ohnivý únik
• 31-Z4-5: Naplnění nádob
• 31-Z4-6: Sčítání škod

31-Z4-1 Nejosamělejší kamarád (8 bodů)

Jak dlouho se už Kevin těšil na dnešek! Je s kamarády na výletě ve Velkoměstě a celý den začnou tím, že si zahrají oblíbenou únikovou hru. Tedy, pokud zvládne dát celou skupinu dohromady, protože po vystoupení z autobusu se všichni nějak rozutekli. Kamarádi se nacházejí v jedné dlouhé ulici, kde jakoukoliv pozici lze popsat číselnou souřadnicí. Vzdálenost mezi dvěma místy tedy určíme jako absolutní hodnotu rozdílu souřadnic.

Máme k dispozici souřadnici každého kamaráda. Který z kamarádů je nejosamělejší, to znamená, že vzdálenost k nejbližšímu jinému kamarádovi je největší? Pokud na jednom místě (na stejné souřadnici) stojí dva nebo více kamarádů, jejich vzdálenost k nejbližšímu kamarádovi je nulová.

Tvar vstupu: Na prvním řádku je číslo N označující počet kamarádů. Na dalším řádku je N souřadnic příslušných kamarádů oddělených mezerou. Všechna čísla jsou přirozená a navzájem různá.

Tvar výstupu: Vypište pořadové číslo nejosamělejšího kamaráda (počítáme od nuly). Pokud je nejosamělejších osob více, vypište pořadové číslo kterékoliv z nich.

5
1 2 11 8 7

2

Řešení

31-Z4-2 Závažíčka na druhou (10 bodů)

Kevin nakonec přece jen kamarády shromáždil a mohli se společně vydat na recepci únikové hry. Recepční je prozatím nechal čekat, protože hra byla zatím obsazena předchozí skupinou. Kevin si všiml zajímavého hlavolamu, který asi měl sloužit na procvičení mysli před začátkem hry.

Hlavolam jsou v podstatě jednoduché váhy, které se vyrovnávají pomocí závažíček. Hmotnost všech závaží, které jsou u vah k dispozici, odpovídá mocninám dvojky: máme tedy závaží o hmotnosti 1, 2, 4, 8, … a tak dále. Platí ale pravidlo, že na levou stranu vah se mohou dávat jen závaží o lichém exponentu mocniny (2¹ = 2, 2³ = 8, 2⁵ = 32, …) a na pravou závaží o sudém exponentu (2⁰ = 1, 2² = 4, 2⁴ = 16, …).

Kevin by chtěl postavit závažíčka na váhy takovým způsobem, aby se hmotnost levé strany vah a pravé strany vah přesně lišila o nějaké celé číslo N. Pokud je N kladné, musí být pravá strana o N těžší než levá, pokud je záporné, musí být levá strana o -N těžší než pravá.

Například pokud dostaneme N = -3, musíme na levou stranu dát závažíčko o hmotnosti 8 (=2³) a na pravou stranu závažíčka 1 (=2⁰) a 4 (=2²).

Abychom dobře otestovali efektivitu vašeho řešení, dostanete na každém vstupu více různých N, u nichž budete muset zjistit rozestavění závažíček.

Tvar vstupu: Na prvním řádku si přečtete číslo K, na dalších K řádcích jsou zapsány rozdíly vah N.

Tvar výstupu: Pro každý z K rozdílů zapište na samostatný řádek binárně, která závažíčka je třeba vložit na váhy a která ne. Konkrétně začnete u nejtěžšího použitého závaží, pokračujete přes všechna lehčí (i nepoužitá) závažíčka a pro každé vypíšete buď 1, pokud jej použijete, nebo 0, pokud nepoužijete. V případě nepoužití žádného závaží vždy vypište 0.

Například pro N=-3 vypíšete jedničku pro 2³ a následně další jedničku pro 2², pokračujete nulou pro 2¹ a skončíte znovu jedničkou pro 2⁰.

4
20
-40
-3
0

10100
101000
1101
0

Řešení

31-Z4-3 Probíhání bludištěm (10 bodů)

Kevin a jeho přátelé se ocitli na startu únikové hry. Nacházejí se v labyrintu tvořeném různě propojenými místnostmi. Z jedné místnosti do druhé lze procházet pomocí dveří, ty lze však použít pouze jednosměrně – na jedné straně dveří je klika, na druhé je „koule“. V každé místnosti jsou dvoje dveře, jedny s klikou a druhé s „koulí“.

Kevin s přáteli si pozorně prohlédli materiály, které obdrželi od recepčního, a zdá se, že našli mapu labyrintu. Kevin by chtěl zjistit, kam se dostane, pokud začne v nějaké místnosti a projde přesně K dveřmi.

Tvar vstupu: První řádek obsahuje počet místností N a číslo K. Následujících N řádků popisuje místnosti. Konkrétně, na i-tém řádku se nachází číslo místnosti, do něž se dostaneme po otevření průchozích dveří v místnosti i. Řádky i místnosti číslujeme od nuly.

Tvar výstupu: Výstup se bude skládat z N řádků. Pro každou místnost vypište číslo místnosti, do které se dostaneme, pokud projdeme K dveřmi.

5 11
4
3
1
2
0

4
2
3
1
0

Řešení

31-Z4-4 Ohnivý únik (12 bodů)

Jednomu z kamarádů se podařilo najít skrytý poklop, skrz který se dalo uniknout z labyrintu. Když ale všichni prolezli východem, ucítili velmi silný zápach spáleniny. Vzápětí uviděli, že budovu, kde se nacházejí, zachvátil požár! Budou si muset zahrát další únikovou hru, jenže tentokrát jsou ve skutečném nebezpečí.

Dostanete k dispozici plán budovy jako čtverečkovanou síť. Každé pole v síti je buď neprůchozí (nachází se tam stěna, sloup atd.), nebo průchozí (jde skrz něj utíkat, ale může se také přes něj šířit oheň). V plánku je dále označena počáteční pozice osoby, jeden nebo více únikových východů a zdroje požáru.

Osoba má za úkol se během několika tahů dostat do jednoho z únikových východů, může však jít jen přes průchozí pole, do nichž se ještě nerozšířil oheň. V každém tahu se osoba pohne o jedno pole (nahoru, dolů, doleva, nebo doprava). Oheň se na začátku hry vyskytuje jenom ve zdrojích požáru, každý další tah se ale rozšíří na všechna pole sousedící vodorovně nebo svisle s alespoň jedním polem, kde už hoří. V poli, kde se nachází oheň, už hořet nepřestane.

V každém tahu se nejprve pohne osoba, až poté se rozšíří oheň. Pozor, počáteční pozice osoby a únikové východy se berou jako průchozí pole, oheň se může skrze ně šířit. Je třeba samozřejmě zařídit, aby oheň nezachvátil pole, na němž právě stojí osoba – jakmile se však osoba dostane na pole s únikovým východem, je zachráněna, i kdyby mělo toto pole hned poté začít hořet.

Tvar vstupu: Na prvním řádku dostanete velikost mapy, tedy počet řádků N a počet sloupců M. Dalších N řádků obsahuje plán budovy. Znak . označuje průchozí pole, # neprůchozí pole, S počáteční pozici, E únikový východ, F zdroj požáru.

Tvar výstupu: Výstup obsahuje nejmenší počet tahů, který je třeba k tomu, aby osoba unikla z budovy. Pokud není možné uniknout, vypište zprávu GAME OVER.

6 5
..F..
E....
....E
F###.
..S..
F....

4

Řešení

31-Z4-5 Naplnění nádob (12 bodů)

Kevin se s kamarády úspěšně dostal k únikovému východu. Než ale budou moci opravdu uprchnout z budovy, musí vyřešit ještě jeden hlavolam.

Před nimi stojí dlouhá řada prázdných nádob, do nichž je možné nalít vodu pouze pomocí speciálního přístroje. Nádoby jsou zleva doprava očíslované a přístroj přijímá příkazy ve tvaru „nalij L litrů vody do souvislé podposloupnosti nádob, která začíná nádobou s číslem A a končí nádobou s číslem B)“.

Máte k dispozici seznam příkazů pro přístroj. Vypočtěte objem vody v každé nádobě po provedení všech příkazů. Musíte počítat s tím, že jak počet nádob, tak počet příkazů může být netriviálně vysoký.

Příklad: Pro 8 nádob a dva příkazy 4 litry do nádob 1 až 4 a 3 litry do nádob 2 až 7 je konečné množství vody v nádobách (popořadě) 0, 4, 7, 7, 7, 3, 3, 3.

Řešení

31-Z4-6 Sčítání škod (14 bodů)

Kevinova parta se nakonec bez úrazu dostala úspěšně z budovy únikové hry. Její majitel teď ale dlouho bude mít těžké spaní, protože celý dům lehl popelem. Naštěstí je pojištěný, ale vzhledem k rozsahu škody bude dlouho trvat, než pojišťovna případ vyřídí. Zatím si majitel alespoň zapisuje do excelovské tabulky hodnotu zničených věcí. Protože jich je velká spousta, v tabulce používá nejen přímé hodnoty zapsané do políček, ale také vzorce, které berou hodnotu z jiných políček.

Pro jednoduchost budeme předpokládat, že každé pole tabulky je buď prázdné, nebo obsahuje celé číslo, nebo je v něm zapsaný vzorec ve tvaru =pole1+pole2. Abychom vyhodnotili pole se vzorcem, musíme nejprve vyhodnotit pole1 a pole2, v nichž může být už konkrétní číslo, nebo další vzorec – ten by potom bylo nutné vyhodnotit dříve.

Dostanete celý popis tabulky. Najděte takové pořadí vyhodnocování polí se vzorci, aby při vyhodnocování kadého pole platilo, že pole na obou stranách sčítání jsou již vyhodnocena. Je možné, že takové pořadí nepůjde najít, v takovém případě to vaše řešení musí umět rozpoznat.

Příklad: V poli A1 je hodnota 3, v poli A2 je uloženo 4, v A3 je zapsáno =A1+A4, v A4 je zapsáno =A2+A1. V takovém případě je třeba nejprve vyhodnotit A4 a až poté A3.

Řešení