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

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

Právě se díváte na leták čtvrté série 34. ročníku KSP-Z, neboli Korespondenčního Semináře z Programování, Začátečnické kategorie. Zapojit se může každý středoškolák i základoškolák, řešit můžete začít i v případě, kdy jste se nezúčastnili prvních tří sérií. Spolu s vydáním této série jsme zveřejnili přihlášku na jarní soustředění v termínu 7. až 14. 5. Přihlásit se můžete na https://ksp.mff.cuni.cz/viz/jarni.

Letos bude v KSP-Z pět sérií po čtyřech úlohách za celkem 220 bodů. Pokud budete mít jakoukoliv otázku, neváhejte se zeptat. Kontaktní adresy najdete v patičce na konci letáku. Přejeme hodně štěstí!

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

• 34-Z4-1: Halleyova kometa
• 34-Z4-2: Letadla na ranveji
• 34-Z4-3: Dozorci v bludišti
• 34-Z4-4: Kamínky

34-Z4-1 Halleyova kometa (8 bodů)

Kevin si zrovna četl o Halleyově kometě a začal přemýšlet nad tím, že určitě existuje spousta lidí, kteří za celý svůj život neměli šanci kometu spatřit. Kolik takových lidí asi může být?

Známe periodu příletů komety a rok, kdy se poprvé objevila. Dále máme seznam N lidí, u kterých známe rok jejich narození a úmrtí. Pomozte Kevinovi zjistit, kolik z nich kometu za svůj život nemohlo spatřit. Pokud se někdo narodil nebo zemřel ve stejném roce, jako se objevila kometa, pak uvažujeme, že ji mohl spatřit.

Toto je praktická open-data úloha. V odevzdávátku si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

Formát vstupu: Na prvním řádku dostanete počet lidí N, periodu komety a rok jejího prvního příletu. Na každém z následujících N řádků bude rok narození a rok úmrtí i-tého člověka. Slibujeme, že žádný člověk nezemřel dříve, než se narodil. Formát výstupu: Na výstup vypište jediné číslo – počet lidí, kteří kometu za celý svůj život nemohli spatřit.

3 5 1
2 4
1 5
5 7

1

Řešení

34-Z4-2 Letadla na ranveji (12 bodů)

Kevin sedí v čekací hale na letišti a pozoruje, jak letadla vzlétají z ranveje. Všiml si, že některá jsou mnohem menší než jiná – ta se patrně hodí na kratší trasy, protože ty delší by s takto malou zásobou paliva nedolétla.

Začal přemýšlet, zda by pouze na základě této znalosti nebyl schopen říci, která letadla odlétají kam.

S největší pravděpodobností se mu nepodaří lety identifikovat jednoznačně, ale aspoň by mohl zjistit, kolik takových možností je.

Kevin pozoruje N odlétajících letadel, u každého je schopen posoudit, na kolik kilometrů vystačí palivo daného letadla. Také zná N cílových destinací, kam letadla poletí. U každé z nich ví i vzdálenost, kterou do této destinace musí letadla doletět. Zároveň ví, že do každé destinace odlétlo právě jedno letadlo (a pochopitelně se nemohlo stát, že by jedno letadlo odlétlo na více míst najednou).

Už však netuší, jak zjistit, kolik je přiřazení letadel k destinacím takových, že žádné letadlo neletí trasu delší, než na kolik mu vystačí palivo. Poradíte mu?

Jelikož počet těchto možností může být obrovský, zajímá nás zbytek po dělení číslem 10⁹ + 7.

Toto je praktická open-data úloha. V odevzdávátku si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

Formát vstupu: Na prvním řádku dostanete počet úkolů T.

Následuje T úkolů, kde každý je zadaný následovně: Na prvním řádku dostanete počet destinací (a počet letadel) N. Na druhém bude N hodnot, kde i-tá udává vzdálenost k i-té destinaci. Na třetím bude N hodnot, kde i-tá udává maximální vzdálenost, na kterou i-tému letadlu stačí palivo. Formát výstupu: Pro každý úkol vypište na samostatný řádek jediné číslo – počet možností, jak letadla korektně přiřadit, modulo 10⁹ + 7.

2
4
3 1 5 2
6 4 1 5
2
5 1
4 4

4
0

Řešení

34-Z4-3 Dozorci v bludišti (12 bodů)

Kevin se po dlouhých odbavovacích procesech na letišti konečně dostal do letadla. Bohužel tím nuda spojená s cestováním nekončí, protože má před sebou dlouhý let. Naštěstí vedle něj sedí Zuzka, která má v batohu šachovnici a pomůže mu krátit čas. Poté, co je omrzely standardní hry na šachovnici, přišla Zuzka s hrou jménem Dozorci.

Stěžejní pro hru je šachovnice, na níž jsou prázdná políčka a políčka zdí. Po prázdných políčkách se pohybují dozorci. Na začátku hry je na šachovnici několik dozorců. Každý dozorce má krom své startovní polohy ještě natočení. Hra se skládá z tahů. V každém tahu každý dozorce provede právě jednu akci. Pokud je na políčku před dozorcem volno (tedy se nejedná o zeď nebo políčko neleží mimo bludiště), dozorce se na něj přesune. V opačném případě zůstane stát na políčku, ovšem otočí se doprava.

Na začátku hry je na každém prázdném políčku nejvýše jeden dozorce, ovšem v dalších tazích už tomu tak být nemusí.

Kevina by zajímalo, jak bude vypadat herní pole po K tazích. Ovšem simulovat hru v hlavě se mu nechce, a tak vás prosí o pomoc.

Toto je praktická open-data úloha. V odevzdávátku si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.

Formát vstupu: Na prvním řádku jsou tři čísla N, M a K oddělená mezerou – rozměry hrací plochy (výška a šířka) a počet tahů simulace. Každý z následujících N řádků obsahuje M znaků reprezentujících hrací plochu. Každý znak reprezentuje jedno políčko. Jejich význam je následující:

• # – Zeď
• . – Prázdné políčko, na kterém není dozorce
• < – Dozorce natočený vlevo
• > – Dozorce natočený vpravo
• A – Dozorce natočený nahoru
• V – Dozorce natočený dolů

Upozorňujeme, že mezi vstupy se vyskytují takové, kde K = 10⁹.

Formát výstupu: Na N řádcích po M znacích vypište herní pole po K tazích. Na výstupu ovšem značte každé políčko, kde je alespoň jeden dozorce pomocí znaku X. Zdi a prázdná políčka zůstávají beze změny.

3 8 3
V>....#V
#.....#.
#.#.<##A

X...X.#X
#..X..#.
#.#..##X

Řešení

34-Z4-4 Kamínky (12 bodů)

Zuzka Kevina porazila v dámě, go, othellu, dozorcích a teď si na něj vymyslela další stolní hru s šachovnicí a herními kameny, které říká kamínky.

Zuzka umístí na dvě šachovnice o rozměrech R×S nerozlišitelné herní kameny. Na jedné z nich je startovní rozmístění, na druhé cílové. Kevinovým úkolem bude přesouvat kameny na té šachovnici se startovní pozicí tak, aby po přesunutí byly rozmístěné stejně jako na šachovnici s cílovou pozicí.

Aby to ale neměl tak jednoduché, může provádět jen určitý typ přesouvání kamenů.

V každém svém tahu si vybere jeden sloupec nebo řádek a kameny v něm zrotuje o libovolné K. To znamená, že všechny kameny v daném sloupci/řádku posune o K polí stejným směrem. Kameny, které by tímto z daného sloupce/řádku vysunul ven, nasune z druhé strany v tom pořadí, v jakém je vysunul.

Například při rotaci následujícího řádku o dva:

.oo.

by dostal následující výsledek.

o..o

Kevin vyhraje, pokud se mu podaří najít nějakou posloupnost tahů (ne nutně nejkratší) takovou, že jimi převede startovní pozici na cílovou.

Může se ale také stát, že Zuzka vytvoří taková rozestavění kamenů, že se nedá z počáteční pozice dostat do cílové pomocí výše uvedených tahů. V takovém případě by to měl Kevin být schopný poznat.

Jelikož je už Kevin unavený z neustálého prohrávání, potřebuje vaši pomoc. Chtěl by algoritmus, kterým když se bude řídit, tak hru vyhraje, popřípadě se dozví, že konkrétní rozestavění nemá řešení.

Poněvadž Kevin není interpret žádného programovacího jazyka, mnohem více než pseudokód ocení srozumitelný popis toho, jak by měl hrát, a zdůvodnění proč to, co by měl dělat, funguje.

Řešení