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.
Řešení ú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ď (Zadání)
Konečnou pozici vesmírné lodi zjistíme tak, že budeme postupně počítat pozice lodi při každé změně rychlosti. Začneme na pozici [0,0] a spočítáme posuny lodi až do času T.
Na začátku máme zadanou rychlost lodi vx, vy. Nyní pro n změn rychlosti spočítáme:
Zjistíme čas c, po který loď touto rychlostí poletí:
kde ti je čas i-tého manévru. Na začátku dosadíme t0=0.
Následně spočítáme novou pozici lodi. Stanovíme změnu v x-ové i y-ové (zx, zy) souřadnici a změnu přičteme k minulé pozici (x, y):
Po každé změně rychlosti spočítáme novou rychlost v obou směrech:
Po dokončení výpočtu nám zbývá zjistit pozici lodi v čase T. Známe její rychlost a pozici po posledním manévru. Stačí spočítat čas, po který loď poletí touto rychlostí, zjistit změnu souřadnic a to přičíst k poslední pozici lodi. Potom budeme znát finální pozici lodi.
33-Z5-2 Přerovnávání čísel (Zadání)
Naším úkolem je seřadit čísla na vstupu tak, aby žádná tři po sobě následující čísla netvořila rostoucí, nebo klesající posloupnost.
Jedním z možných přístupů je postupně generovat všechna možná uspořádání (permutace) čísel na vstupu, a pro každou vygenerovanou permutaci zkontrolovat, zda neobsahuje žádná tři po sobě jdoucí klesající či rostoucí čísla. Algoritmus skončíme ve chvíli, kdy nalezneme první permutaci splňující výše uvedené podmínky.
Tento přístup má však jeden háček. Existuje celkem N! permutací vstupních čísel a většina těchto permutací je špatná – nesplňuje výše uvedené podmínky. Během našeho algoritmu tedy strávíme nejvíce času generováním posloupností, které následně zahodíme.
Dalším možným řešením je kontrolovat permutaci již při jejím generování. V případě porušení zadání pak můžeme permutaci zamítnout ještě předtím, než ji celou vygenerujeme. Při generování využijeme rekurzivní přístup, kdy budeme zkoušet budovat posloupnost přidáváním čísel ze vstupu na konec posloupnosti. Pokud přidané číslo poruší zadání, vrátíme se v rekurzi o krok zpět. Uvědomte si, že to nemusí znamenat odebrání jednoho čísla, ale třeba odebrání několika čísel (v krajním případě i zahození celé dosud vybudované posloupnosti), pokud jsme vyzkoušeli, že permutace s naším aktuálním začátkem nedokážeme správně dokončit.
Obě předchozí řešení se snaží řešit problém hrubou silou, neboť systematicky prochází prostor všech možných řešení problému, který může být velmi velký. Nedokážeme najít nějaký systém v tom, jak takové „správné“ permutace vypadají? Můžeme si všimnout, že posloupnost splňující zadání je vlastně tvořena střídáním „malých“ a „velkých“ čísel. Jak si ale takové dvě skupiny čísel vytvořit? Nejjednodušší variantou, která navíc programátorovi ušetří případnou další kontrolu nad posloupností čísel, je seřadit si posloupnost vstupních čísel vzestupně a rozdělit setříděnou posloupnost na dvě stejně velké skupiny. Pokud máme lichý počet čísel, bude první skupina obsahovat o jedno číslo více. Následně budeme střídat vypisování čísel z první a z druhé skupiny.
Otázkou zůstává, zda bude takto vytvořená posloupnost splňovat zadání? Můžeme si všimnout, že pro každé číslo z druhé skupiny platí, že je větší než libovolné číslo z první skupiny. Zároveň pro každé číslo z první skupiny platí, že je menší než libovolné číslo z druhé skupiny. Pokud tedy za sebe seřadíme číslo z první skupiny, číslo z druhé skupiny a následně číslo z první skupiny, nikdy nemůžeme dostat tři po sobě jdoucí rostoucí čísla. Obdobné tvrzení platí pro trojici sestávající z čísla z druhé skupiny, první skupiny a druhé skupiny.
Nejvíce časově náročnou operací je seřazení pole, které zabere O(N log N), výpis čísel totiž zvládneme v čase lineárním s velikostí vstupu.
33-Z5-3 Hledání min v chodbě (Zadání)
Když bychom hráli hledání min, snažili bychom se umístění min odvodit logicky. Nás program může postupovat stejně. Nejprve si představme, že víme, zdali se nachází mina pod prvním políčkem. Zbytek již dokážeme odvodit.
Číslo nad prvním políčkem udává počet min pod prvním a pod druhým políčkem. Jenže my už víme, kolik min je pod prvním políčkem. Rozdíl těchto hodnot nám řekne počet min pod druhým políčkem.
Pokračujeme druhým políčkem, kde využijeme podobný postup. Číslo nad ním nám řekne celkový počet min pod třemi políčky. Pro první dvě z nich už víme, jestli pod nimi miny jsou nebo ne. Dopočítáme, jestli je mina i pod posledním políčkem.
Takto postupně vyplňujeme zleva doprava. Vždy známe informace o předchozích dvou políčkách a z toho jsme schopni dopočítat další.
Jak však vyřešíme první políčko? U něj si můžeme jednoduše tipnout. Pokud bychom si tipli špatně, v průběhu dalšího vyplňování by nám vyšlo, že pod nějakým políčkem musí být 2 miny nebo -1 min. V takovém případě začneme odznovu, jen zvolíme druhou možnost.
Číslo nad posledním políčkem nám už ve vyplňování nijak nepomůže, o existenci poslední miny se totiž rozhodneme již na předchozím políčku. Musíme však ještě dodatečně zkontrolovat, že je správně. Mohlo by se totiž stát, že není, to by také znamenalo, že jsme první minu tipli špatně.
33-Z5-4 Záznam cesty (Zadání)
V našem řešení se budeme inspirovat prohledáváním do šířky (více v grafové kuchařce). Nejprve si ke každému vrcholu (křižovatce) poznamenáme číslo 0. Dále si pořídíme frontu. Každý její prvek bude obsahovat dva záznamy, a sice nějaký vrchol našeho grafu a pořadí v posloupnosti kódů (pozpátku), kdy jsme se ve vrcholu mohli nacházet. Zprvu ve frontě bude jediný prvek, cílový vrchol s nulou.
Teď budeme odebírat prvky z fronty a posouvat se příslušným způsobem, pozpátku, v posloupnosti kódů. Pro každý takto odebraný vrchol se podíváme na vrcholy, do kterých z něj vedou hrany. Takové vrcholy, které jsou označené aktuálním kódem v naší posloupnosti, přidáme do fronty a přepíšeme jejich číslo na aktuální pořadí v posloupnosti. Pokud už vrchol aktuálním pořadím označený byl, neděláme nic, abychom pro daný krok měli ve frontě každý odpovídající vrchol jen jednou. Všimněme si, že s takovým postupem budou čísla pořadí ve frontě jedině stoupat. Nestane se, že bychom po odebrání vrcholu čtvrtého kroku narazili ještě na vrchol kroku třetího.
Jakmile ve frontě narazíme na vrchol s pořadím, které už odpovídá začátku cesty dolem, stačí vypsat všechny možné počáteční vrcholy. Celkově můžeme říct, že jsme provedli K kroků a v každém jsme až z N vrcholů navštívili až M hran, čímž dojdeme k časové složitosti O(K(N+M)). Lepší odhad nenajdeme, protože tato mez se nabyde pro úplný graf (kde z každé křižovatky vede chodba do každé jiné) se stejným kódem ve všech křižovatkách.