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

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

Vítejte u páté série 33. ročníku KSP-Z, neboli Korespondenčního Semináře z Programování, Začátečnické kategorie.

Tato série je poslední z letošních pěti sérií KSP-Z, takže máte ještě poslední šanci získat nějaké body v KSP-Z, ke kterým budeme přihlížet při výběru účastníků podzimního soustředění, které se snad bude konat normálně fyzicky.

Pokud budete mít jakoukoliv otázku, neváhejte se zeptat. Kontaktní adresy najdete v patičce letáku. Přejeme hodně štěstí!

• Termín série: neděle 23. května ve 32:00 (tedy další ráno v 8:00), praktické úlohy za třetinu bodů až do 30. května
• Odevzdávání: elektronicky přes Odevzdávátko
• Jak sepsat řešení: viz ukázková úloha MO-P
• Dotazy ohledně zadání: posílejte na ksp@mff.cuni.cz, nebo se ptejte na Discordu KSP.

Zadání úloh

• 33-Z5-1: Vesmírná loď
• 33-Z5-2: Přerovnávání čísel
• 33-Z5-3: Hledání min v chodbě
• 33-Z5-4: Záznam cesty

33-Z5-1 Vesmírná loď (8 bodů)

Vesmírný superhrdina Kevin se vydal vstříc Největšímu Záporákovi, aby zachránil své přátele Sáru a Petra. Právě nyní však kličkuje mezi vesmírnými minami Největšího Záporáka a nemá úplně čas sledovat, kde se právě nachází.

Naštěstí však ví, odkud přesně svou vesmírnou lodí odstartoval, a palubní počítač mu na děrný štítek tiskne všechny provedené změny rychlosti. Po dokličkování by Kevin rád věděl, kde přesně se jeho loď právě nachází.

Pohyb Kevinovy vesmírné lodi si můžeme představit jako pohyb po dvourozměrné mřížce s osami x a y. Na začátku loď startuje v pozici (0,0) s rychlostí v_x (o kolik políček se posune v ose x za jednu sekundu) a v_y (to samé pro osu y). Loď pak v určitých časech provádí změny své rychlosti.

Například pro počáteční rychlost v_x=5, v_y=-2 se v čase 5 dostane na pozici (25, -10). Když pak v této sekundě přijde změna rychlosti v ose x o -4 a v ose y o 2 (tedy rychlost se změní na v_x=1, v_y=0), tak se po dalších 5 sekundách v čase 10 ocitne na pozici (30, -10). Vaším úkolem bude spočítat, na jaké pozici se bude loď nacházet v čase T, který dostanete na konci vstupu.

Formát vstupu: Na prvním řádku dostanete tři čísla: číslo N udávající počet změn rychlosti a čísla v_x a v_y udávající počáteční rychlost v osách x a y. Na dalších N řádcích pak vždy dostanete tři čísla popisující manévr: číslo t udávající čas manévru a čísla d_x a d_y udávající změnu rychlosti v obou osách. Manévry budou uspořádané podle t a nikdy neproběhnou dva manévry ve stejný čas. Na posledním řádku pak dostanete číslo T (větší než čas posledního manévru) udávající čas, ve kterém nás zajímá pozice vesmírné lodi. Všechny časy, rychlosti i jejich změny budou celá čísla.

Formát výstupu: Na jediný řádek výstupu vypište dvě čísla oddělené mezerou udávající pozici vesmírné lodě v čase T.

3 5 -2
5 -4 2
10 2 17
11 -4 -17
15

29 7

Řešení

33-Z5-2 Přerovnávání čísel (10 bodů)

O né, Největší Záporák nalíčil na Kevina past a polapil ho! Kevin se ocitl ve vězení společně se Sárou a Petrem. Největší Záporák však netušil, že Sára zamlada řešila KSPčko a je tak docela zkušeným hackerem a Kevinovi se povedlo do vězení propašovat malý počítač.

Pro obejití bezpečnostního systému musí Sára poskládat za sebe řadu různých čísel, čímž odemkne zámek jejich cely. Bohužel jsou v systému kontroly, které spustí alarm, pokud budou jakákoliv tři čísla po sobě rostoucí (tedy a < b < c), nebo naopak pokud budou jakákoliv tři čísla po sobě klesající (tedy a > b > c).

Vaším úkolem bude pro vstup tvořený z N různých celých čísel vypsat ta stejná čísla na výstup, ale v takovém pořadí, aby nenastala ani jedna z výše uvedených situací (tedy tři po sobě rostoucí nebo klesající čísla).

Formát vstupu: Na prvním řádku vstupu bude číslo N, na druhém řádku pak bude N různých mezerou oddělených čísel.

Formát výstupu: Na jediný řádek výstupu vypište stejných N čísel ze vstupu, ale v pořadí splňujícím výše popsané podmínky. Správných řešení může být více, vyberte si libovolné z nich.

9
2 13 15 1 4 21 7 9 14

4 13 7 9 1 21 2 15 14

Poznámka: Naopak řešení 4 13 9 7 1 21 2 15 14 by bylo chybné, protože 13, 9 a 7 jsou tři po sobě jdoucí klesající čísla. U výstupu 4 13 7 9 1 21 2 14 15 by zase byl problém s rostoucí trojicí 2, 14 a 15.

Řešení

33-Z5-3 Hledání min v chodbě (12 bodů)

Superhrdinovi Kevinovi a jeho přátelům se povedlo uniknout z cely ven, ale pořád nejsou z tajné základny Největšího Záporáka venku. Nejkratší cesta ven vede přes zaminovanou chodbu. A zaminovaná chodba nezískala svůj název jen tak pro nic za nic …

Chodba je rozdělena na dlaždice a pod každou z nich se může nacházet mina. Naštěstí se Petr zamlada díval na seriál MacGyver a teď díky zmagnetizovanému kovovému prachu, tabulce čokolády a tkaničce od bot zvládl zjistit, kolik min je v těsném okolí každé dlaždice (počítaje i dlaždici samotnou).

Pro každou dlaždici tak dostáváte číslo udávající počet min ve vzdálenosti nejvýše jedna od ní. Číslo může být v rozsahu od 0 (žádná mina pod dlaždicí ani pod jejími sousedy) do 3 (mina pod dlaždicí, pod jejím levým sousedem i pod jejím pravým sousedem).

Vaším úkolem bude z těchto čísel zjistit, pod kterými dlaždicemi jsou miny umístěné.

Formát vstupu: Na prvním řádku vstupu dostanete číslo N udávající délku chodby. Na druhém řádku pak dostanete N čísel v rozsahu 0 až 3 udávající počet zjištěných min v těsném okolí každé z dlaždic.

Formát výstupu: Na jediný řádek výstupu vypište řetězec N znaků bez mezer udávající rozmístění min v chodbě, které odpovídá číslům ze vstupu. Pro políčko bez miny vypište znak ., pro políčko s minou znak M.

12
012221212232

..MM.M.M.MMM

Řešení

33-Z5-4 Záznam cesty (14 bodů)

Vesmírný superhrdina Kevin unikl i se svými přáteli ze základny Největšího Záporáka sítí bývalých důlních chodeb. Kevin si cestou stihl zaznamenávat písmenkové kódy nakreslené na stěnách křižovatek, kterými probíhali skrz. Po příchodu na povrch pak vytáhl mapu dolu a pokusil se z jejich cesty rekonstruovat, kde asi mohl být tajný východ ze základny Největšího Záporáka, kterým do sítě chodeb vstoupili.

Mapu důlních chodeb si můžeme představit jako graf s křižovatkami jako vrcholy a chodbami jako hranami vedoucími mezi vrcholy. U křižovatek navíc známe jejich kódy, ale stejný kód se typicky nachází u více křižovatek (tedy nemusí být unikátní).

Kromě mapy ještě dostaneme označený cílový vrchol, do kterého Kevin došel, a také posloupnost kódů křižovatek tak, jak je Kevin cestou zaznamenával.

Vaším úkolem je vymyslet algoritmus, který pro zadanou mapu, cílový vrchol a posloupnost kódů najde všechny vrcholy, ve kterých mohl Kevin začít a přitom cestou ke konečnému vrcholu projít křižovatkami se zadanými kódy. Kevin mohl jít jakkoliv (vracet se stejnou cestou, navštívit tutéž křižovatku vícekrát, …), ale kód křižovatky si zapsal pokaždé, když do nějaké došel.

Zkuste u svého algoritmu odhadnout časovou složitost, neboli řádově kolik kroků musí vykonat pro graf s N vrcholy a M hranami a pro posloupnost dlouhou K kódů.

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/kurzy/zkp/.

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í.

Řešení