Třetí série začátečnické kategorie dvacátého sedmého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Řešení úloh
- 27-Z3-1: Kevin nabíječ, s.r.o.
- 27-Z3-2: Nedej vitagen
- 27-Z3-3: Superstromy
- 27-Z3-4: Robo Rally
- 27-Z3-5: Dřevěná slacklajna
- 27-Z3-6: Red Bull dává křídla
27-Z3-1 Kevin nabíječ, s.r.o. (Zadání)
Když jste nad úlohou chvíli přemýšleli, případně si zkoušeli různá zapojení, asi jste přišli na to, že na způsobu zapojení vůbec nezáleží, dokud budou všechny prodlužovačky připojeny k té jedné ve zdi. Každá prodlužovačka jednu zdířku použije pro své napájení a k jich poskytne pro libovolné další použití. Pokud použijeme všechny dostupné prodlužovačky, můžeme prostě spočítat součet všech k - 1. To uděláme nejsnáze tak, že sečteme všechna k a na konci odečteme N (a přidáme jedničku za zásuvku ve zdi).
V zadání byl ale malý háček, který jsme se snažili naznačit obrázkem. Kevin si nakoupil i prodlužovačky, které měly nula zdířek, a takové zapojovat nechceme. Takže je stačí prostě z řešení vynechat. Tento chyták byl jen v posledním testu, takže i pokud jste si ho nevšimli, mohli jste dostat většinu bodů. Na takové chytáčky si ale dávejte pozor.
27-Z3-2 Nedej vitagen (Zadání)
Maximální délka slova na vstupu byla v zadání 100. To je dostatečně malá konstanta na to, abychom se jí nemuseli zabývat. Soustředíme se hlavně na to, aby náš program byl co nejrychlejší vzhledem k počtu slov na vstupu.
Připravíme si spojový seznam všech zadaných slov a druhý spojový seznam, ve kterém budou také všechna slova, akorát napsaná pozpátku. Teď stačí jen najít slova, která jsou v obou seznamech.
To se dá dělat více způsoby. Nejsnazší je prostě každé slovo z prvního seznamu porovnat se všemi ze druhého a zapsat si ho stranou, pokud se s nějakým shoduje. To by mělo časovou složitost O(N2), kde N je počet slov na vstupu.
O něco mazanější a výrazně rychlejší způsob je oba seznamy setřídit abecedně a potom je šikovně zkoumat najednou. Na třídění posloupnosti je spousta algoritmů, které skončí v čase O(N log N).
Jak přesně tedy budeme seznamy prohlížet? Budeme postupně procházet oba seznamy najednou a v každém kroku se podíváme na první slova v obou seznamech. Pokud jsou stejná, nalezli jsme požadovanou shodu. Jinak z nich vybereme to lexikograficky menší (neboli to, které by se ve slovníku objevilo dřív) a to smažeme. Tím se v tomto seznamu posuneme o jedno dál.
Pokaždé tak pracujeme pouze se začátkem nějakého spojového seznamu, což je velmi rychlé, protože nahlédnutí na první prvek i jeho smazání ve spojovém seznamu trvá konstantní čas (nezávisí na velikosti seznamu).
Pokud je nějaké slovo v obou seznamech, někdy během mazání se stane, že oba dva seznamy budou mít toto slovo na začátku. Proto stačí před každým mazáním zjistit, jestli se náhodou slova na začátcích seznamů neshodují. Mezi dvěma mazáními slov provedeme konstantní počet operací a mazání je 2N, všechna dohromady budou tedy trvat O(N). Z toho plyne, že časová složitost celého algoritmu je O(N log N + N) = O(N log N).
Najít mezi nimi to nejdelší už je triviální, můžeme to dělat třeba tak, že si v průběhu pamatujeme jenom dočasného adepta na vítěze a přepíšeme ho leda delším slovem.
27-Z3-3 Superstromy (Zadání)
Podle počtu správných řešení se zdá, že jste s úlohou neměli příliš problémů. Ono také nebylo potřeba vymýšlet nic světoborného. Stačilo si jen uvědomit, že si nikdy neuškodíme tím, že stromy rostoucí pomalu zasadíme jako první.
Proč to platí? Vždy alespoň jeden strom doroste jako poslední. Jak bychom mohli naše řešení zlepšit? Jedině tím, že tento poslední strom zasadíme v nějaký dřívější den. Pokud jsme však v dřívějších dnech sázeli pouze pomalejší stromy, prohozením si párty akorát odložíme na později.
Optimální pořadí stromů tedy dostaneme tak, že si je seřadíme sestupně dle počtu dní, které rostou. Následně jen stačí najít maximum ze součtu doby růstu a čísla dne, ve který daný strom zasadíme.
Dostali jsme tak řešení s časovou složitostí O(N log N) a paměťovou O(N). To bohatě stačilo na plný počet bodů. Kdo si však všiml nízkého limitu na dobu růstu, mohl řešení o něco vylepšit.
Protože existuje pouze T = 1 000 různých typů stromů, můžeme si v poli velikosti T uložit, kolik kterých z nich máme. Díky tomu zvládneme čísla třídit v čase O(N + T). Dokonce si i vystačíme jen s O(T) pamětí, protože si nemusíme pamatovat celý vstup.
Ačkoli popsaná myšlenka není vůbec složitá, vysloužila si svůj vlastní název. Takovému třídění čísel se říká counting sort. Vyplatí se jej použít v případech, kdy chceme seřadit velké množství stejných hodnot.
Program – counting sort (Python 3)
27-Z3-4 Robo Rally (Zadání)
V této úloze stačí vymyslet, jak v programu reprezentovat herní plochu a roboty a krok po kroku odsimulovat, co se děje.
Je mnoho možností, jak k problému přistoupit. Hlavní je nějakým způsobem
reprezentovat robota, třeba jako objekt nebo klidně jako seznam čísel
udávajících jeho pozici a orientaci. Například seznam [7, 1, 2, D] by mohl
reprezentovat robota číslo 7, který je v prvním řádku, druhém sloupci a dívá se
směrem dolů.
Potom stačí vymyslet, kam roboty dát. Je rozumné mít je v poli indexovaném podle jejich identifikátorů, abychom se snadno dostali k robotovi, kterého zrovna potřebujeme.
Často navíc budeme zjišťovat, co je na nějakém políčku. Nejjednodušší způsob je prozkoumat souřadnice všech robotů a zjistit, jestli se nějaká neshoduje se zkoumaným políčkem. To by ale mohlo trvat dlouho a děláme to často. Pokud nám záleží na rychlosti, můžeme si udělat pomocné dvourozměrné pole, kde na každém políčku bude číslo robota, který na něm je (nebo rovnou odkaz na něj), nebo -1 (resp. nulový odkaz), pokud tam žádný není.
Teď už nebude problém načíst pozice a orientace robotů a umístit je do naší datové struktury. Otáčení robotů je taky triviální. Pokud směry reprezentujeme písmeny, stačí k tomu několik podmínek. Pokud reprezentujeme směry čísly 0, 1, 2, 3, můžeme si pomoci operací modulo, která nám umožní zjistit zbytek po dělení čtyřmi. Tedy když se chceme otočit o tři doprava, tak k současnému směru přičteme trojku a výsledek vymodulíme čtyřmi.
Zajímavější je pohyb. Musíme si dát pozor, že je potřeba simulovat krok po kroku. Tedy posun o pět políček budeme muset rozložit na pět kroků a každý vyhodnotit zvlášť. Pokud nám v nějakém kroku nestojí nic v cestě, tak je to snadné. Stačí přepsat posunutému robotovi souřadnice a případně upravit pomocnou tabulku.
Pokud nám stojí něco v cestě, řekneme tomu, ať udělá krok stejným směrem a podle stejných pravidel jako my. Tedy pokud mu bude stát něco v cestě, tak tomu taky řekne, ať se to posune. Takto se o tom dozví celá řada. Je důležité ošetřit případ, kdy se řada už nemá kam posunout (je před ní zeď). Kvůli tomu je potřeba ještě před samotným posunem nejdříve ověřit, zda se vůbec můžeme pohybovat, a teprve potom posun provést.
Po provedení všech kroků stačí vypsat postupně souřadnice a orientace robotů.
27-Z3-5 Dřevěná slacklajna (Zadání)
Jak už všichni víme z hodin matematiky, trojúhelník, jehož nějaká strana je delší než součet všech ostatních, nejde nakreslit. A stejně tak to platí i pro mnohoúhelník. Kdyby Kevin se Sárou položili všechna prkna kromě nejdelšího za sebe do jedné linie a tato linie by byla kratší než ono nejdelší prkno, nemohou si okruh vůbec vyrobit.
Základem řešení bude tedy tato myšlenka. Délky prken si nejprve setřídíme, ideálně od největšího po nejmenší. Součet všech délek označíme S, délku nejdelšího prkna D.
Pokud je:
- S-D > D, okruh lze postavit ze všech prken, jejichž délka je D nebo menší.
- S-D ≤ D, tak nejdelší prkno nelze použít. Od S odečteme D a celé porovnání provedeme znova, akorát D již bude délka dalšího nejdelšího prkna v pořadí.
Na konci stačí zkontrolovat, že nám zbyla alespoň tři prkna, ze kterých může Kevin se Sárou okruh postavit.
Časová složitost bude O(N log N), kde N je počet prken. Projití setřízeného seznamu délek prken bude lineární, jelikož pro každé prkno provedeme pouze konstantně mnoho operací. Ovšem setřízení prken bude trvat O(N log N).
27-Z3-6 Red Bull dává křídla (Zadání)
Nedostali jsme příliš mnoho řešení, což nás mrzí. Pojďme si ukázat, že tato úloha nebyla tak těžká, jak se vám možná zdála.
Jelikož procházíme stavovým prostorem (což neznamená nic jiného, než že máme hrací plochu a na každém políčku můžeme být buď jako král, nebo jako kůň), tak si musíme rozmyslet, jak jej budeme reprezentovat.
Pro tuto konkrétní úlohu se nám zdá vhodné mít dvě dvourozměrná pole, která budou odpovídat velikosti hrací plochy, tedy velikosti M×N.
Jedno pole bude pro místa, kam jsme došli jako král, a druhé bude pro místa, kam jsme došli jako kůň.
Vždy z každého dosaženého políčka zkusíme jít do všech políček ve druhém poli, na která se daná figurka může dostat a ještě jsme tam nebyli. (Ve druhém poli, protože se tahy koněm a králem střídají.)
To, jestli jsme v některém stavu už byli, si budeme značit číslem udávajícím, v kolikátém kroku jsme tam došli. Což nám pomůže při debugování, neboť víme, kam nám to kdy skočilo. Ale taky podle toho dokážeme zrekonstruovat cestu.
Pro nalezení cesty pak stačí jít z cíle do startu po stavech, která mají právě o jedna menší číslo, než ve kterém jsme. Před výpisem tuto posloupnost musíme ještě otočit. Rozmyslete si, že v tomto případě nelze udělat trik, že bychom hledali cestu z cíle do startu, a tím se vyhnuli otáčení posloupnosti.
Posledním krokem je si rozmyslet, jak rychle zjistit, kam jsme již skočili. Nejlepší bude si to pamatovat v nějaké struktuře, do které budeme umět v konstantním čase vkládat prvky na konec a vyjmout první prvek. Takové struktuře se říká fronta.
Nyní již jen zbývá zanalyzovat, jak dobrý algoritmus jsme vymysleli. Projití všech stavů nám bude trvat O(N · M), protože právě tolik je stavů a v každém stavu děláme konstantní množství operací, a stejně tolik paměti budeme potřebovat.
Závěrem ještě dodáme, že použít jen jedno společné pole pro kroky koněm i králem nestačí, protože na tom, jakou figurkou jsme se do které pozice dostali, závisí i následné možné pohyby z tohoto políčka dál. A pokud políčka zvládneme dosáhnout ve dvou různých tazích koněm i králem, tak je nutné zkoumat obě varianty. Zkuste si to třeba na příkladu Kevina na pozici 5×5 a cíle na pozici 2×2. Na takovéto políčko se dá dostat za 3 tahy, ale pokud bychom neuvažovali obě možnosti (pokud bychom použili jen jedno společné pole dosažitelnosti), tak nám algoritmus bude říkat, že se tam dostaneme za 4 tahy.