Třetí série začátečnické kategorie dvacátého šestého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Řešení úloh
- 26-Z3-1: Zámky labyrintu
- 26-Z3-2: Čarodějova šifra
- 26-Z3-3: Hádanka
- 26-Z3-4: Tvar labyrintu
- 26-Z3-5: Ceny na střelnici
- 26-Z3-6: Horská dráha
26-Z3-1 Zámky labyrintu (Zadání)
Stejně tak, jako zadání znělo jednoduše, řešení bude též jednoduché.
Nejprve si musíme rozmyslet, na jaké hodnoty bychom potenciálně měli nastavit a, b a c.
| c+a |
| 2 |
Tedy stačilo spočítat tyto hodnoty, a pak zjistit, kde je v absolutní hodnotě nejmenší rozdíl s původní hodnotou.
26-Z3-2 Čarodějova šifra (Zadání)
Než jsme se mohli pustit do samotného šifrování mřížkou, bylo nutné poradit si se situací, kdy jsme měli text kratší, než kolik byla velikost mřížky (K × K). Dalo by se to řešit nějakou soustavou podmínek až přímo při šifrování, ale proč si to komplikovat?
Nejjednodušší řešení jsou často ta nejlepší – prostě si na začátku doplníme text na požadovanou délku opakováním písmen „KSP“. Na technické detaily, stejně jako na detaily načítání vstupu se můžete podívat do vzorových programů na konci tohoto řešení.
Tím se dostáváme k hlavní části celé úlohy, k šifrování mřížkou. Řešme nejdříve jednodušší případ bez otáčení a pak zkusme stejný princip zkombinovat s otáčením.
Máme tedy dvourozměrné pole s mřížkou a text. Budeme si udržovat pozici v textu – jaké písmeno bychom měli zapsat dál – a budeme postupně po sloupcích a řádcích procházet dvourozměrné pole s mřížkou (vnější cyklus přes řádky, vnitřní přes sloupce, abychom šli správně zleva doprava řádek po řádku). Vždy, když narazíme na díru, zapíšeme na stejnou pozici ve výsledném dvourozměrném poli písmenko, které je zrovna na řadě (a posuneme ukazatel na další). Tak postupně projdeme celou mřížku a máme jednu čtvrtinu úkolu splněnou.
Teď by se nám líbilo mřížku otočit a to celé provést znova. Můžeme si buď celou mřížku nakopírovat a otočit, nebo můžeme transformovat souřadnice až při jejím otáčení. Je důležité si uvědomit, že když mřížku otočíme doprava (po směru hodinových ručiček), je to to samé, jako když souřadnice transformujeme na druhou stranu, doleva. Když se ptáme, co je na souřadnicích [r,s] v mřížce otočené o jedna doprava, můžeme náš dotaz přeložit na ekvivalentní dotaz: co se nachází na souřadnicích otočených o jedna doleva v původní mřížce.
Ať už se rozhodneme pro jeden nebo druhý způsob, budeme potřebovat nějaký přepočet souřadnic pro otočení, neboli na jaké pozici se octne to, co bylo původně na souřadnicích [r,s]. Ukážeme vzorce pro otočení doprava, pro otočení doleva je to stejné, jen odzadu (jedno otočení doleva je to samé jako tři otočení doprava). Indexujeme tabulku od nuly, takže máme sloupce i řádky s indexy 0,…,K-1.
- otočení doprava: [r, s] →[s, K-1-r]
- otočení doprava: [r, s] →[K-1-r, K-1-s] (vlastně první otočení aplikované dvakrát)
- otočení doprava: [r, s] →[K-1-s, r] (to samé, jen třikrát)
Teď již máme všechny potřebné stavební kameny. Stačí jen čtyřikrát provést zapsání přes mřížku a mezitím otáčet (ve vzorových programech používáme variantu s transformací souřadnic). Díky vlastnostem mřížky slíbeným v zadání jsme zapsali na každé políčko výsledné tabulky právě jeden znak a tím jsme splnili čarodějovo zadání, stačí mu tedy mřížku odevzdat (vypsat) a můžeme jít dovádět do Labyrintu snů.
26-Z3-3 Hádanka (Zadání)
Nejdříve si připomeneme kritérium dělitelnosti devíti, které asi všichni znají: číslo je dělitelné devíti beze zbytku právě tehdy, když ciferný součet jeho zápisu (v desítkové soustavě) je také dělitelný devíti. Například číslo 738 je dělitelné devíti právě proto, že ciferný součet 7+3+8 = 18 devíti dělitelný je.
Než se pustíme do samotné úlohy, dovolím si drobnou otázku. Zamýšleli jste se někdy nad tím, proč toto kritérium funguje? Pokud ne, ukážeme si to. Vezmeme si naše známé číslo 738, budeme ho postupně dělit devíti a budeme sledovat přenosy mezi řády.
Rozepíšeme si číslo po řádech na 7 · 100 + 3 · 10 + 8 · 1 a budeme ho postupně zkoušet dělit od největšího řádu (jako bychom popořadě dělili jednotlivé členy čísly 900, 90 a 9). Dělení 900 nám nic nezmění, ale už dělení 90 je zajímavé. To nám zruší první člen a z každé stovky nám zbude právě jedna desítka, tedy přičteme 7 k desítkám (dostáváme tak 10 · 10 + 8 · 1). Když budeme dál dělit 9, zmizí nám desítkový člen a z každé desítky nám zůstane právě jedna jednička, dostaneme tedy výraz 18 · 1 a u něho už dělitelnost devíti snadno poznáme.
Asi jste si už všimli jisté pravidelnosti. Je to dáno tím, že číslo v n-ární (přesněji desítkové) soustavě dělíme číslem n-1 (tedy devítkou). Z každého řádu se nám tak přenese do nižšího právě takové číslo, které v něm je. A všechny tyto přenosy se pak shromáždí v jednotkovém řádu, což je přesně ekvivalentní cifernému součtu.
Potom, co jsme si dokázali dělitelnost devíti, přejděme už k řešení samotné úlohy. V podstatě nám stačí na místa otazníků doplnit taková čísla, aby nám ciferný součet vyšel dělitelný devíti. Zároveň ale chceme, aby číslo bylo co nejmenší možné, takže chceme umisťovat co nejmenší čísla do velkých řádů.
S výjimkou pozice na začátku čísla, kde musí být alespoň jednička, můžeme jinak zkusit všude místo otazníků doplnit nuly. Pokud nám potom vyjde ciferný součet dělitelný devíti, vyhráli jsme, pokud ale ne, bude ještě nutné číslo upravit.
Stačí si ale spočítat, kolik nám schází do nejbližšího dalšího čísla dělitelného devíti, to je maximálně osm. Takže nám stačí nějaké zapsané číslo (nulu nebo jedničku) zvětšit o osm. A protože chceme výsledné číslo co možná nejmenší, provedeme to u nejméně významného řádu – u nejpravější pozice s otazníkem.
Všechno, co potřebujeme, je několikrát projít všechny cifry čísla. Takže pro číslo dlouhé N cifer zabere náš postup čas O(N). Nahlédněte do vzorových programů.
26-Z3-4 Tvar labyrintu (Zadání)
Struktuře křižovatek a cest mezi nimi se v informatice říká graf, a takto speciálnímu grafu bez cyklů potom strom. Problém ze zadání je tedy problém nalezení nejdelší cesty (trasy) ve stromu.
Představme si křižovatky a slepé cesty jako uzlíky a cesty mezi nimi jako provázky odpovídající délky. Potom celý labyrint uchopme za křižovatku s číslem 0 a nechme provázky s uzlíky volně spadnout dolů. Pokud si to dokážete představit, můžete si všimnout následujících faktů. Nejdelší cesta bude vždy končit ve slepé chodbě – pokud do křižovatky vedou alespoň dvě chodby a jednou z nich přijdeme, tak není důvod se zastavovat, když můžeme druhou odejít. Další pozorování je, že uzlík, který spadnul nejníže (je tedy nejvzdálenější od křižovatky 0), bude určitě na kraji té nejdelší cesty. Kdybychom poté celý strom chytili za tento nejhlubší uzlík a zase nechali ty ostatní volně spadnout dolů, už bychom snadno nalezli nejdelší cestu.
Jak to ale udělat algoritmicky? Nalézt nejhlubší uzlík zvládneme průchodem grafu do hloubky, problém je ale s „přetočením“ stromu pod nejhlubší uzlík. Proto si vysvětlíme snadněji naprogramovatelný postup.
K tomu si zavedeme několik pojmů, vyjdeme u nich z představy zavěšených uzlíků. Podstrom začínající v nějakém uzlíku u je strom obsahující tento uzlík a vše, co visí pod ním, uzlík u je kořenem tohoto podstromu. Svislá cesta je pak taková trasa, která v tomto zavěšení vede pouze dolů. Stojí za všimnutí, že libovolnou jinou cestu můžeme získat složením dvou svislých cest.
Při zpracování každé křižovatky uvažujeme pouze podstrom s kořenem v této křižovatce. Spočítat chceme dvě věci: jednak délku nejdelší svislé cesty, jednak délku nejdelší cesty procházející kořenem (tedy zpracovávanou křižovatkou).
Rekurzivně získáme délky nejdelších svislých cest vedoucích ze sousedních křižovatek, k nim přičteme vzdálenost k příslušné křižovatce. Maximum z těchto hodnot představuje délku nejdelší svislé cesty, součet dvou největších hodnot je pak délkou nejdelší cesty procházející přes kořen. Pro úplnost dodejme, že nejdelší svislá cesta vycházející ze slepé uličky má délku 0.
Pokaždé, když počítáme cestu procházející přes kořen, porovnáme navíc výsledek s globálně udržovaným maximem, a je-li větší, toto maximum upravíme. Po zpracování celého stromu v něm tak máme hledanou délku nejdelší cesty ve stromu.
Ještě bychom si měli rozmyslet složitost. Do každé křižovatky určitě přijdeme jen jednou (do každé vede shora maximálně jedna chodba). Jejím zpracováním strávíme jednak nějaký konstantní čas, jednak nějaký další konstantní čas za každou chodbu, která z křižovatky vede dolů. Všimněme si ovšem, že když do každé křižovatky vede nejvýše jedna chodba, je chodeb nejvýše N. Dohromady tak potřebujeme čas O(N). Podobně paměťová složitost je lineární.
26-Z3-5 Ceny na střelnici (Zadání)
Pomalu, ale jistě
Hledáme v zadané posloupnosti a co nejdelší úsek, ve kterém jsou všechny prvky různé. Zkusíme nejdřív najít nejdelší takovýto úsek, který začíná na prvním prvku, tedy zcela vlevo.
To je velice jednoduché, stačí si nějak v paměti udržovat, které všechny různé prvky jsme už potkali. Pokud budeme mít druhy cen označené přirozenými čísly, tak se na to skvěle hodí pole. Vytvořme si pole c, ve kterém na začátku budeme mít všude nuly (to znamená, že jsme zatím nic nenavštívili), a pokud potkáme cenu označenou i, napíšeme do c nějaké nenulové číslo na c[i].
No a pokud budeme chtít zapsat na místo, kde už ale něco nenulového je, znamená to, že jsme právě přečtenou hodnotu potkali už podruhé. Takže úseky od začátku na místo, na které se budeme dívat, od teď budou určitě obsahovat dvojici stejných prvků.
Ale tím nesmíme ukončit hledání, ještě je možnost, že existuje nějaký vyhovující úsek začínající někde dál než na prvním prvku. Nejjednodušší způsob by byl použít stejný algoritmus od druhého prvku, potom od třetího, potom od čtvrtého a tak dále až do N-tého. To by ale trvalo moc dlouho – algoritmus spustíme N-krát a může zkoumat až N prvků, takže časová složitost bude O(N2). Pro první úkol ale stačí, protože pokaždé algoritmus skončí po nejvýše padesáti krocích (delší úsek různých cen nemůže být). Proto bude časová složitost O(50N)=O(N).
Optimalizace
My ho ale dokážeme výrazně zrychlit jednoduchým trikem: Když budeme do pole chtít napsat, že jsme potkali nějakou cenu x na pozici i, na c[x] zapíšeme hodnotu i. Tedy o druhu ceny x budeme vědět nejen, že jsme ho potkali, ale i kde to naposledy bylo.
Algoritmus bude postupovat tak, že bude procházet posloupnost cen a u každé zjistí, kde začíná nejdelší úsek různých cen, který v ní končí. Pokud prozkoumáme novou cenu, tento začátek nejdelšího úseku zůstane buď stejný jako u předchozí, nebo se posune někam směrem doprava.
Když přijdeme k nějaké ceně x na pozici i, zjistíme, jestli je její poslední výskyt před nebo za začátkem nejdelšího úseku končícího na pozici i-1. Pokud je před ním, můžeme ho ignorovat a začátek bude pro i stejný jako pro i-1. Pokud bude za ním, posune se tím začátek nejdelšího úseku doprava těsně za poslední výskyt.
Tímto způsobem projdeme postupně celou posloupnost a budeme si udržovat zatím nejlepší délku úseku, jakou jsme dosud viděli. Spolu s ní si zapamatujeme i indexy jejího začátku a konce. Ty přepíšeme, jakmile potkáme nějakou lepší.
Proč to celé funguje?
Sluší se ještě dokázat, že jsme žádnou ještě lepší validní posloupnost nepřehlédli. Na každém prvku posloupnosti jsme znali nejdelší posloupnost, která na tomto místě končí (kdybychom se pokusili její začátek posunout o jedno místo doleva, objevila by se mezi prvky posloupnosti nějaká dvojice – právě na takové místo jsme začátek posouvali).
Konec posloupnosti jsme v průběhu algoritmu posouvali postupně o jedničku, proto, ať by nejlepší validní podposloupnost končila kterýmkoliv prvkem, tak bychom přes něj museli přejít a podposloupnost bychom tak našli.
Jak dlouho to celé poběží? Uděláme N kroků, kde krok je všechno, co uděláme mezi jednotlivými posunutími konce posloupnosti. Tam ale uděláme vždy konstantní počet operací, takže časová složitost bude O(N).
26-Z3-6 Horská dráha (Zadání)
Hlavním nástrojem, který využijeme v této úloze, je třídění. O rychlých třídících algoritmech se dočtete třeba v naší kuchařce.
V prvním úkolu stačí všechny hodnoty, které si Kevin zapsal, vzestupně setřídit. Poté budeme zleva doprava hodnoty procházet a udržovat si přitom počítadlo, které bude obsahovat délku souvislého úseku složeného ze stejných hodnot, ve kterém se právě nacházíme. Pokud je následující hodnota stejná jako předchozí, počítadlo o jedna zvětšíme, jinak jej vynulujeme. Zároveň si v průběhu udržujeme dosavadní maximální hodnotu počítadla, kterou stačí aktualizovat vždy před vynulováním a pak na konci.
Výpočet se skládá ze dvou fází: třídění a následný průchod. První fáze nás stojí při použití rychlého třídícího algoritmu O(N log N) času, druhá fáze už jen O(N), takže celková časová složitost tohoto algoritmu je pak O(N log N).
Budeme předpokládat, že se horská dráha chová rozumně spojitě, tedy pokud jsme přejeli z výšky a do výšky b, ocitli jsme se přitom jednou v každé výšce mezi a a b. Navíc úsek mezi každými dvěma Kevinovými zápisy je ze zadání celý z kopce nebo celý do kopce, takže každý úsek mezi dvěma zápisy můžeme popsat intervalem, jehož krajními hodnotami jsou ony zapsané hodnoty.
Rádi bychom nyní řekli, že hledaná výška je taková, která je obsažena v nejvíce intervalech. To je ovšem zrádné, protože místa, ve kterých si Kevin zapisoval výšku, jsou zachycena ve dvou intervalech. Lokální výškové extrémy tedy určitě nebudou dobrými kandidáty na hledanou nejčastěji navštěvovanou výšku. Představme si třeba obyčejnou sinusoidu, na které by se Kevin vyskytl ve výšce 0 mnohem častěji než ve výšce 1. Raději bychom proto počítali s otevřenými intervaly.
Učiníme pozorování, které nám to umožní: představme si, že jsme již nalezli onu výslednou výšku, ale vyskytuje se na seznamu, tedy je koncovým bodem některých intervalů. Bez újmy na obecnosti předpokládejme, že se tato výška vyskytuje v nejvýše tolika lokálních údolích jako vrcholech (jinak pokračujeme obráceně). Pak ovšem můžeme tuto výšku zmenšit o dostatečně malinké číslo, čímž sice už nebude v údolích, ale za každý vrchol teď budeme mít dva výskyty této výšky v jeho blízkém okolí. Jeden bude nalevo a jeden napravo. Celkový počet výskytů se tedy nezmenšil a dostali jsme výšku, která leží pouze v otevřených intervalech (volbou dostatečně malého zmenšení jsme se mohli všem ostatním lokálním extrémům vyhnout).
Nyní nám stačí pracovat s otevřenými intervaly a budeme postupovat podobně jako v první úloze. Vezmeme si všechny konce intervalů, přidáme ke každému konci příznak, zda je to konec levý nebo pravý, a všechny konce vzestupně setřídíme.
Setříděné pole budeme procházet zleva doprava a udržovat si, v kolika jsme zrovna intervalech. Pokud narazíme na levý konec, počítadlo o jedna zvýšíme, pokud narazíme na pravý, o jedna jej zmenšíme. Přitom si udržujeme maximální hodnotu počítadla tentokrát ještě navíc s intervalem, ve kterém jí bylo dosaženo. Ten vznikne jako průnik nějakých intervalů, při výpočtu jej však snadno dostaneme jako největší levý a nejmenší pravý konec, který aktuálně máme.
Nakonec máme interval (a,b), který reprezentuje výšky, ve kterých jsme se nejčastěji objevili. Stačí tedy vypsat libovolnou z nich, třeba (a+b)/2, což je určitě číslo z vnitřku intervalu.
Časová složitost tohoto algoritmu je stejná jako v prvním úkolu, tedy O(N log N).