Čtvrtá 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.

Právě se k vám dostala poslední série začátečnické kategorie tohoto ročníku KSP. Doufáme, že jste všichni zdrávi a že vám rozptýlení v podobě další várky úloh přijde vhod.

Zapojit se může každý středoškolák i základoškolák a to i v případě, kdy jste se nezúčastnili předchozích sérií. 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ě zdaru s úlohami!

• Termín série: neděle 21. června ve 32:00 (tedy další ráno v 8:00), praktické úlohy za třetinu bodů až do 28. června
• 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

• 32-Z4-1: Jednobarevné praní
• 32-Z4-2: Hoří chleba?
• 32-Z4-3: Esej do bloku
• 32-Z4-4: Bomberman uklízí
• 32-Z4-5: Kopečková zmrzlina
• 32-Z4-6: Trojjediné mince

32-Z4-1 Jednobarevné praní (8 bodů)

Kevin se při návštěvě koupelny podíval na rostoucí hromadu prádla přetékající prádelní koš a zapřemýšlel, jestli je to zatím největší hromada triček, kterou poslední dobou viděl.

Při rozdělování domácích prací v době domácí karantény dostal totiž Kevin na starost praní triček. Aby si to co nejvíce ulehčil a neriskoval, že obarví své bílé tričko svým zeleným tričkem, tak si zavedl jednoduchý postup: Vždycky, když se sešlo 5 triček stejné barvy, tak je dal hned vyprat.

Poznamenával si, jak barevná trička mu postupně do (na začátku prázdné) hromady přibývala a nyní by ho zajímalo, kolik nejvíce triček se na hromadě v jednu chvíli sešlo.

Tvar vstupu: Na prvním řádku vstupu dostanete číslo N udávající počet triček, která postupně přibývala do hromady. Na druhém řádku pak bude následovat N velkých písmen anglické abecedy oddělených mezerou udávajících barvy triček.

Tvar výstupu: Na výstup vypište maximální počet triček, jež se nacházely v jednu chvíli na hromadě. Pokud se na hromadě sešlo 5 triček stejné barvy, tak je nejdříve započítejte do maxima a až pak dejte vyprat.

12
B C B B B B D C A C A A

7

Nejdříve se sešlo 6 triček, ale pak jsme 5 z nich vyprali, takže maxima 7 jsme dosáhli až na konci.

Řešení

32-Z4-2 Hoří chleba? (10 bodů)

Kevinova malá sestra Zuzka má ráda pečení a teta, u které teď jsou, než zase otevřou školy, peče a dodává do malé vesnické pekárny. Tohle všechno Kevinovi proběhlo hlavou, když vyšel z koupelny, kde právě naplnil pračku, do chodby zaplněné troubami na pečení. Jenže prakticky ze všech trub se začínalo kouřit a po chvilce se začaly rozeznívat i jednotlivé hlásiče požáru, co v dlouhé chodbě byly.

Potom, co s tetou zažehnali katastrofu a vše uhasili, tak se Kevin zamyslel, v jakém pořadí se rozeznívaly hlásiče.

V dlouhé chodbě, kterou si můžeme představit jako řadu políček na kostičkovém papíře, jsou na nějakých políčkách rozmístěné trouby a požární hlásiče. Všechny trouby začaly v tu samou chvíli kouřit a kouř se z nich síří rychlostí jednoho políčka za vteřinu (v první sekundě je kouř jenom na políčku trouby, ve druhé už i na sousedních políčkách v obou směrech a tak dále).

Hlásič ale sepne až ve chvíli, kdy se k němu dostane kouř od alespoň dvou trub. Pro zadanou chodbu s troubami a hlásiči bychom chtěli vědět pořadí, v jakém se hlásiče rozezní.

Tvar vstupu: Na prvním řádku vstupu dostanete číslo N udávající počet objektů v chodbě. Na dalších N řádcích bude vždy souřadnice (číslo políčka) a písmeno T nebo H udávající, jestli je na tomto políčku trouba nebo hlásič. Souřadnice budou v pořadí od nejmenší po největší.

Tvar výstupu: Na výstup vypište na samostatné řádky hlásiče (určené jejich souřadnicemi) v pořadí, v jakém se rozezní. Pokud se ve stejnou chvíli rozezní více hlásičů, tak je uveďte v pořadí od nejmenší souřadnice.

7
1 H
3 T
4 T
4 H
7 H
10 T
11 H

4
1
7
11

Hlásič 4 se rozezní ve druhé sekundě, hlásiče 1 a 7 se rozezní ve čtvrté sekundě a hlásič 11 se rozezní v osmé sekundě.

Řešení

32-Z4-3 Esej do bloku (10 bodů)

Kevin už doufal, že po vyklizení doutnajících zbytků chleba ze všech trub bude mít klid. Ale jen co sedl k počítači, překvapil ho email od jeho kamarádky Sáry, ve kterém ho prosila o zformátování eseje na dějepis.

Poslala Kevinovi esej napsanou na jednom dlouhém řádku a potřebovala by ji zformátovat tak, aby byla zarovnaná do bloku na požadovanou šířku. Zarovnání do bloku na šířku K v tomto případě znamená, že:

• Všechny řádky mají právě K znaků (počítáme i mezery).
• Na každém řádku je maximální možný počet slov, který se na řádek vejde.
• Každý řádek začíná a končí slovem a jednotlivá slova jsou od sebe oddělena jednou nebo více mezerami.
• Mezery mezi slova rozmisťujeme tak, aby byly počty mezer mezi slovy na jednom řádku stejné. Pokud počet mezer nevychází na šířku řádky, tak prvních několik slov od sebe může být odděleno o jednou mezerou více než zbylá slov (počet mezer tak může být například 5 5 4 4 4).
• Výjimka: Pokud vyjde jen jedno slovo na řádek, tak ho umístěte na začátek řádku a doplňte mezerami.

Tvar vstupu: Na vstupu dostanete na prvním řádku číslo N udávající počet slov a číslo K udávající požadovanou šířku řádku. Na druhém řádku pak bude následovat N mezerami oddělených slov sestávajících z malých písmen anglické abecedy. Slova nikdy nebudou delší než K písmen.

Tvar výstupu: Na výstup vypište naformátovaný text na řádky široké právě K znaků tak, aby obsahoval všechna slova ze vstupu v nezměněném pořadí a zároveň aby splňoval podmínky uvedené výše.

15 17
zlata bula byla prijata
v roce dvanactset
dvanact a urcila
premysla otakara za
ceskeho krale

zlata  bula  byla
prijata   v  roce
dvanactset
dvanact  a urcila
premysla  otakara
za  ceskeho krale

Poznámka: V ukázce máme vstupný text na více řádcích, aby se nám vešel do letáku. Ve vstupech ale bude vždy na jednom řádku.

Řešení

32-Z4-4 Bomberman uklízí (12 bodů)

Později večer si Kevin plánoval zahrát s Petrem hru Bomberman přes internet. Bohužel ale Petrovi vypadlo připojení, tak si nějakou dobu hrál Kevin sám. Pokoušel se vždy vyčistit celou mapu od zdí.

Hra Bomberman se hraje na čtverečkovém plánku, kde jsou skály (ty nejdou rozbít), zdi (ty rozbít jdou) a volná políčka (po těch se dá chodit). Hráč vždy dojde na nějaké políčko, položí na políčko bombu, poodejde někam dál a pak bombu odpálí. Bomba pak vybuchne ve čtyřech směrech (nahoru, dolů, doleva a doprava) a zasáhne nejbližší neprázdné políčko v tom směru – pokud to je skála, tak se nic nestane, pokud to je zeď, tak se z ní stává volné políčko (a pokud to je hráčova postavička, tak hráč umírá).

Vaším úkolem bude pro zadanou mapu vyrobit posloupnost příkazů, kterými vaše postavička „odbouchne“ všechny zdi na ní, ale sama přitom neumře. Všechny příkazy jsou jednopísmenné a jsou to: příkazy

• N, D, L, P – pohyb Nahoru, Dolů, vLevo a vPravo o jedno políčko
• B – položení bomby
• O – odpálení bomby dálkovým ovládáním

Posloupnost příkazů nemusí být nejkratší ani nemusí mít jiné speciální vlastnosti, stačí jakákoliv posloupnost příkazů, která odbouchne všechny zdi a ne vás.

Tvar vstupu: Na prvním řádku budou čísla R a S udávající počet řádků a sloupců mapy. Na dalších R řádcích pak bude vždy S znaků. Znak # znamená nezničitelnou skálu, znak * znamená zničitelnou zeď, znak . znamená prázdné místo a znak P je počáteční políčko, kde začíná vaše postavička.

Tvar výstupu: Na jediný řádek výstupu vypište (bez mezer) jednotlivé kroky, které vaše postavička musí udělat pro „odbouchnutí“ všech zdí. Výstup by se měl vejít do 1 MB (naše testovací řešení nachází posloupnosti kroků do 100 KB).

4 9
P.#..*...
..#..#*..
*....##..
*....*#..

BDPODDBPPNONNBDPONPPBPDO

Řešení

32-Z4-5 Kopečková zmrzlina (12 bodů)

Další den dostali Kevin se Zuzkou od své babičky kopečkovou zmrzlinu v kornoutu. Zuzka ale byla velmi vybíravá, prý přímo na kornout smí přijít jenom čokoládová nebo vanilková, na vanilkovou smí přijít čokoládová nebo jahodová, na čokoládovou jahodová, citrónová nebo už přímo poleva a tak dále.

Kevin si všechna pravidla zapsal a překvapilo ho, jak je v nich Zuzka konzistentní – při skládání kopečků podle těchto pravidel se nikdy nešlo vrátit ke stejné příchuti znova (informaticky řečeno v pravidlech nebyl žádný cyklus).

Kevina by zajímalo, kolik různých kornoutů se zmrzlinou se dá podle těchto pravidel sestavit. Kornout se zmrzlinou začíná vždy kornoutem a končí polevou. Pravidla jsou ve tvaru „Na X může příjít jenom A, B, C, …“, na polevu již nic přijít nemůže a kornout se zmrzlinou bez polevy není správný a nebudeme ho počítat.

Vymyslete algoritmus, který pro takto zadaná pravidla spočítá, kolik různých kornoutů lze poskládat.

Řešení

32-Z4-6 Trojjediné mince (14 bodů)

Další večer si Kevin opět volal přes internet s Petrem. Petr objevil u nich na půdě truhlu plnou starých mincí. Podle Petra to byla směs tří druhů mincí, které jsou sice na první pohled nerozpoznatelné, ale mají různou váhu.

Aby Petr Kevina trochu potrápil, tak mu poslal seznam vážení, která provedl. Petr si mince očísloval a pak vždy vybral dvě mince, porovnal jejich váhy a výsledek si zapsal (tedy že první byla těžší, druhá byla těžší, nebo že obě vážily stejně). Tento seznam vážení pak Petr poslal Kevinovi.

Kevin by teď měl jen s pomocí tohoto seznamu vážení určit, která mince patří do které hromádky – pomozte mu na to navrhnout algoritmus.

Váš algoritmus dostane seznam provedených vážení (o kterém slibujeme, že k jednoznačnému určení hromádek stačí) a měl by vydat tři množiny mincí. Zároveň by měl provést nějaký rozumný počet kroků (tedy řešení zkusit všechny možnosti rozdělení do hromádek nebude to správné). V této úloze po vás tedy budeme chtít i dobře odhadnout, kolik kroků výpočtu bude vás algoritmus muset udělat (pro N mincí a řádově N vážení).

Řešení