První 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-Z1-1: Na zastávce
- 27-Z1-2: Kalkulačka
- 27-Z1-3: Slovník T9
- 27-Z1-4: Lyžař
- 27-Z1-5: Cédéčko z koncertu
- 27-Z1-6: Žárovky
27-Z1-1 Na zastávce (Zadání)
Autobusovou úlohu vyřešíme tím nejjednodušším postupem, jaký vůbec může být: přímou simulací. To znamená, že v programu budeme provádět operace odpovídající tomu, co by se dělo v reálném světě (nástup skupinky do autobusu, odjezd autobusu), jednu po druhé ve stejném pořadí, v jakém by se odehrály doopravdy.
Samozřejmě většina programovacích jazyků neumí pracovat ani s lidmi, ani s autobusy, tak si místo toho pořídíme několik číselných proměnných, které budou náš svět popisovat:
- počet lidí v autobusu stojícím na zastávce
- počet autobusů, které již odjely
- pořadové číslo skupinky, která je aktuálně na začátku fronty
Nyní stačí postupně projít všechny skupinky a pro každou z nich upravit tyto proměnné tak, aby popisovaly situaci po odbavení dané skupinky dle pravidel v zadání. To je poměrně přímočaré a podrobněji si to můžete prohlédnout v ukázkovém programu.
Pozor je třeba dát si zejména na „plus/minus jedničkové“ chyby: tedy například nezapomenout započítat i poslední nezaplněný autobus, nebo naopak pokud se poslední autobus zcela zaplní, nezapočítat navíc ještě jeden prázdný.
Přímá simulace obvykle nepatří mezi nejefektivnější řešení, ale v případě naší úlohy jím je. Časová složitost řešení je lineární v počtu čekajících skupinek, a lépe to určitě nejde, neb v kratším čase by program ani nestihl přečíst svůj vstup.
27-Z1-2 Kalkulačka (Zadání)
Myšlenkový postup řešení úlohy s kalkulačkou byl přímočarý, stačilo jen postupně načítat operátory a čísla a provádět s nimi zadané operace. Důležité ale bylo rozmyslet implementační detaily.
Načítat čísla a operátory ze vstupu je nejlepší dělat v cyklu – a to buď v lichých krocích čísla a v sudých operátory, nebo rovnou v každém kroku celou dvojici čísla a operátoru.
Ať to budeme provádět jakkoliv, jeden krok výpočtu vždy provedeme ve chvíli načtení dalšího čísla. V nějaké proměnné si budeme držet dosavadní výsledek, pak se podíváme na operátor (abychom nemuseli psát série if-podmínek, nabízejí některé jazyky zkratku konstrukcí switch) a provedeme to, co je po nás požadováno. Zde je také správné místo k ošetření dělení nulou, při dělení nulou neprovedeme nic.
Zbývají dvě otázky. První z nich je, kdy provádět vypisování mezivýsledků. Zadání úlohy vyžadovalo, abychom mezivýsledek vypisovali při každém načtení operátoru. Stačí si uvědomit, že to je to samé, jako když mezivýsledek vypíšeme ve chvíli jeho spočítání (protože další na vstupu přijde vždy operátor), a tak to také uděláme.
Poslední věcí je, jak výpočet odstartovat a jak ukončit. Ukončení je jednoduché,
budeme i '=' brát jako operátor, jen se speciálním významem ukončení programu
(všimněte si, že výsledek k tomuto operátoru už vypsala poslední operace).
Začátek výpočtu je složitější, protože vždy po načtení nového čísla chceme provést výpočet. Jaký ale provést pro první číslo? Abychom to nemuseli řešit speciální podmínkou, inicializujeme na začátku proměnnou s výsledkem na nulu a operátor na plus. A to je celé, na implementaci se podívejte v programech níže.
27-Z1-3 Slovník T9 (Zadání)
Začneme tím, že každé slovo přeložíme na jeho zápis v T9. Poté čísla rozdělíme do skupin tak, aby v jedné skupině skončila slova, která se v T9 píší stejně. A nakonec najdeme největší skupinu.
Jak to udělat konkrétně? V Pythonu si můžeme pořídit slovník, jehož klíče budou jednotlivé zápisy v T9. Ke každému klíči přiřadíme pole, kam budeme ukládat všechna slova s tímto zápisem. Pak už jenom projdeme všechny klíče slovníku a najdeme ten, jehož pole je největší.
Rozmysleme si, jak rychlé naše řešení bude. Každá operace se slovníkem zabírá v průměru lineární čas s délkou klíče, nezávisle na tom, jak je slovník velký. (Slovník uvnitř funguje jako hešovací tabulka. Pokud vás zajímají detaily, nakoukněte do kuchařky o hešování. Zde stačí vědět, že hešovací tabulky dovedou být velice rychlé, ale jenom v průměru; nejhorší případ může být až lineární s velikostí slovníku.)
Celý program proto poběží v průměrně lineárním čase se součtem délek všech slov, tedy s velikostí vstupu.
Na Céčkovém řešení si předvedeme jiný přístup: nejprve vytvoříme dvojice
(původní slovo, převedené slovo). Pak tyto dvojice setřídíme podle
převedených slov – můžeme se inspirovat kuchařkou
o třídění, případně použít knihovní funkci qsort.
Setříděním se dostanou k sobě slova se stejným zápisem, takže je snadno poznáme a najdeme největší takovou skupinu.
Opět si rozmysleme časovou složitost. Setřídění n hodnot kvalitním třídicím algoritmem (třeba MergeSortem) trvá O(n log n) porovnání, projití setříděného slovníku spotřebuje dalších O(n) porovnání. A jelikož zadání omezuje slova na 15 písmen, můžeme předpokládat, že slova umíme porovnávat v konstantním čase. Časová složitost proto činí O(n log n).
27-Z1-4 Lyžař (Zadání)
Nejprve si pojďme rozmyslet, jak bychom řešili situaci pro kopec výšky dva, který by vypadal třeba takto:
1
2 3
U takového kopce se stačí podívat doleva a doprava, a kde je vyšší číslo, tam pojedeme. Teď si pojďme ukázat, že i z velkého kopce se dá postupně vyrobit kopec výšky dva. Nejprve si to ukážeme na kopci výšky tři:
1
2 3
3 2 1
Pro snazší orientaci budeme jednotlivá místa na kopci označovat podle toho, v kolikáté jsou řadě seshora, a v kolikáté jsou řadě zleva, zapisovat to budeme jako [3,1] (což v tomto případě značí trojku ve třetím řádku vlevo).
Nejprve se podíváme na místo [2,1]: Kdyby kopec začínal zde, stačí se podívat jen doleva a doprava dolů a víme, kam se máme z tohoto místa vydat. Tedy k místu [2,1] přičteme hodnotu v místě [3,1], protože je větší než v místě [3,2].
Teď si představíme, že kopec začíná v místě [2,2], a provedeme pro něj stejný postup jako pro místo [2,1] (jen k němu přičteme hodnotu z [3,2], protože je větší než v [3,3]). Nyní můžeme zapomenout na třetí řádek, protože už víme, do kterých míst se nám vyplatí jet z druhého řádku.
Po zapomenutí třetího řádku máme opět kopec výšky dva a pro něj už umíme zjistit řešení jednoduše. Tento postup ale nezáležel na tom, že je kopec vysoký zrovna tři řady. Když tento postup zobecníme, budeme umět vyřešit i kopec libovolné výšky.
Konstrukce zespodu
Zkusíme tedy zobecnit postup pro kopec výšky tři na kopec výšky N. Budeme ho postupně zespodu snižovat:
- Pro i od 1 do N-1:
- max ← maximum z [N,i] a [N,i+1]
- [N-1,i] ←[N-1,i] + max
Na poslední řádek teď můžeme zapomenout. Tímto z kopce výšky N vyrobíme kopec výšky N-1 a opakováním postupu se dostaneme až na kopec výšky jedna, který už je sám o sobě řešením.
Tento postup bude pro kopec výšky N trvat O(N2), protože na každé místo se podíváme maximálně třikrát a všech míst je dohromady O(N2).
Řešení, které jsme si právě předvedli, se dá považovat za jednu z technik dynamického programování, neboli skládání řešení velkých problémů z řešení malých.
Rekurzivní náhled
Druhý náhled na úlohu může být shora dolů. Kdybychom znali maximální součet na celé cestě začínající pod námi vlevo nebo vpravo, tak bychom si z nich už snadno vybrali, kam se máme vydat.
Toho můžeme využít pro řešení pomocí rekurze. Pokaždé se našeho programu zeptáme, jaký je součet vlevo a vpravo, porovnáme je, a pak jako výsledek vrátíme součet toho většího z nich a hodnoty v aktuálním místě.
Jen to nelze naprogramovat takto přímo. Kdybychom totiž pokaždé počítali výsledek pro všechna nižší místa, výpočet by se spouštěl pro každé místo mnohokrát. Kolikrát přesně může nastínit schéma níže. Znalejší z vás si možná všimli, že je to vlastně Pascalův trojúhelník:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
. . . . . .
Vidíte, že počet rekurzivních volání roste velmi rychle. Na prvním řádku se ptáme na dvě hodnoty pod námi, na druhém se ptáme na tři hodnoty pod námi, z toho ale na jednu dvakrát, na třetím řádku se ptáme již čtyřikrát, na čtvrtém osmkrát a tak dále.
Dalo by se napsat, že se na i-tém řádku ptáme řádově na 2i hodnot pod námi, což nám dává celkovou časovou složitost O(2N). Druhý možný náhled dávající stejnou složitost vypadá tak, že se podíváme na možné cesty, kudy se můžeme vydat. Při cestě dolů z kopce se na každém místě rozhodujeme mezi dvěma směry a toto rozhodnutí děláme N-krát, což nám opět dává O(2N) možností.
Abychom tak zbytečně mnohokrát nepočítali něco, co už víme, vždy si vypočtenou hodnotu uložíme do pomocného pole stejné velikosti, jako má sjezdovka, a zapamatujeme si, že pro tuto cestu již výsledek známe.
Když se pak v programu budeme ptát na hodnotu cesty, nejprve zjistíme, jestli už ji máme spočítanou, a pokud ano, jen vrátíme výsledek. Jinak spočítáme cestu, uložíme výsledek opět do pole a zapamatujeme si, že už pro toto místo cestu spočítanou máme.
Na každé místo se tak budeme ptát maximálně dvakrát, což bude trvat O(N2), neboli lineárně s velikostí vstupu. Lépe to jistě nepůjde, neboť vstup musíme určitě přečíst celý. Kdybychom ho celý nečetli, můžeme do některého nepřečteného místa dosadit dostatečně velkou hodnotu, aby změnila optimální cestu, ale náš program by takové změněné řešení neměl jak poznat.
Ukázali jsme tedy dvě různá řešení, která ve výsledku vedou k něčemu velmi podobnému. První implementaci jsme ukázali již výše, na druhou se můžete podívat zde:
27-Z1-5 Cédéčko z koncertu (Zadání)
Pomalé řešení
Ze zadání víme, že máme najít souvislý úsek písniček takový, že součet jejich délek je přesně K. Písniček je N, a tak si můžeme zvolit až N různých písniček, kterými by CDčko mohlo začínat. Ke každému možnému začátku existuje až N možných posledních písniček, což nám dává řádově N2 možností (dvojic začátků a konců). Tak si je zkusme všechny projít a pro každou spočítat délku písniček mezi nimi (včetně jich samotných).
Jak to provedeme? Pojedeme v nějakém cyklu začátkem přes celou posloupnost písniček, v něm dalším cyklem přes možné konce a v každém takovém úseku ještě třetím cyklem spočítáme součet délek všech v něm obsažených písniček. Spočtení každého úseku bude trvat čas O(N), a pro N2 úseků tedy celkově O(N3).
To se nám ale moc nelíbí, tak to zkusíme zlepšit použitím prefixových součtů z naší základní kuchařky. Čas potřebný na spočítání úseku se tím sníží na O(1) a celkově tedy na O(N2), ale stále zbytečně počítáme pořád dokola skoro ty stejné věci. Ovšem my máme rádi rychlé algoritmy, nedá se to tedy zlepšit?
Zrychlujeme
Algoritmus bude pracovat následovně. Budeme mít tři proměnné: začátek a a konec b, které budou ukazovat na první, respektive poslední písničku aktuálního úseku, a součet S délek písniček aktuálního úseku (na začátku bude velký jako délka první písničky). V každém kroku výpočtu porovnáme S s číslem K, mohou nastat tři možnosti:
- S = K: V tomto případě jsme vyhráli a nalezli jsme úsek se součtem K začínající písničkou a a končící b.
- S < K: Zde vidíme, že se nám na CD ještě něco vejde, tak zkusíme přidat další písničku. To znamená, že konec úseku posuneme o jednu písničku dál (b zvýšíme o jedna) a délku b-té písničky přičteme k S. Opakujeme porovnání.
- S > K: Tady už přidání další písničky nemůže pomoci (rozdíl by se pouze zvětšoval), tedy víme, že a-tou písničkou nemůže hledaný úsek začínat. Ovšem další písničkou ano, proto od S odečteme délku a-té písničky a a posuneme o jednu pozici dál na následující písničku. Opakujeme porovnání.
Pokud začátek nebo konec chceme posunout, ale už není na jakou písničku, tak ohlásíme, že neexistuje úsek písniček, který by bylo možné na CD zapsat (ve skutečnosti stačí kontrolovat pouze konec, neboť pokud bychom a zvýšili tak, že by „ukazovalo“ na neexistující písničku, tak by byl součet nulový, a tedy bychom posouvali b).
Důkaz správnosti
Algoritmus úspěšně seběhl, tak si ověřme, že bude fungovat vždy. Už víme, že možných úseků je řádově N2, musíme je ale procházet všechny? Pokud je součet našeho úseku od a do b příliš velký, tak odebráním první písničky současně vyřadíme všechny další nezkontrolované úseky začínající touto písničkou (zkontrolovali jsme jenom úseky končící maximálně v b).
Ovšem každý takový úsek by měl součet určitě delší než úsek (a, b), který už sám byl příliš dlouhý. Vyloučili jsme tedy jen úseky, které by nás stejně nezajímaly.
Obdobným argumentem se můžeme podívat na posouvání b o jedna dál (všechny vyloučené ještě nezpracované úseky by byly příliš malé). Náš algoritmus tak vylučuje pouze ty úseky, u nichž už víme, že by nevyhovovaly. Všechny ostatní zkontrolujeme, tudíž pokud řešení existuje, najdeme ho.
Už víme, že algoritmus funguje, tak se pojďme podívat, jak dlouho mu to trvá. Při hledání úseku v každém kroku posuneme a nebo b o jedna dál, písniček je N, každá může být nejvýše jednou označena jako a a nejvýše jednou jako b. Tedy nejpozději po 2N krocích dojdeme na konec a ukončíme prohledávání. Celý algoritmus má tedy časovou složitost O(N).
27-Z1-6 Žárovky (Zadání)
Pre lepšie pochopenie riešenia si trošku upravíme zápisy. Ku žiarovkám pridáme ešte jednu, ktorá bude stále svietiť, pomenujme ju žiarovka Nádej.
Pôvodný počet žiaroviek si označíme ako n-1 a pridaním Nádeje budeme mať n žiaroviek. Nádej vždy svieti, a teda nám problém úlohy s n-1 žiarovkami upravuje na problém s n žiarovkami. Prečo tomu tak je? V pôvodnom prípade rozsvecujeme žiarovky v počtoch 0, 1, 2, … , n-1. V druhom prípade to upravíme na 1, 2, … , n, čo je vlastne Nádej + (0, 1, 2, … , n-1).
Zjednodušená úloha
Úlohu si na začiatok ešte trošku zjednodušíme. Obmedzíme počet žiaroviek len na mocniny dvojky (1, 2, 4, 8, … ). Na túto zjednodušenú úlohu použijeme nasledovný algoritmus:
- Žiarovky si rozdelíme na dve časti (polovice).
- K časti, ktorá neobsahuje Nádej, pridelíme jeden spoločný vypínač.
- Ak časť obsahuje len Nádej, tak program ukončíme (táto žiarovka už nepotrebuje vypínač, lebo sa nedá vypnúť). Inak opakujeme algoritmus od kroku jedna zavolaním sa na časť obsahujúcu Nádej.
Naším prvým krokom bude ukázať, že takéto rozdelenie vypínačov je správne – teda, že rozsvieti ľubovoľný počet žiaroviek z intervalu 1 až n. Využijeme k tomu indukciu. Mať rozsvietenú práve jednu žiarovku vieme pomocou žiarovky Nádej, pričom všetky ostatné vypínače sú vypnuté.
Implikáciu ukážeme takto: ak vieme postupne rozsvietiť k/2 žiaroviek (do stavu 1 až k/2 rozsvietených) a zároveň máme vypínač, ktorý rozsvieti druhú polovicu (teda presne k/2 žiaroviek), tak vieme rozsvietiť aj ľubovoľný počet žiaroviek od 1 do k. Stačí nám na to rozsvietiť druhú polovicu jedným vypínačom. A potom k takto rozsvietenej polovici vieme pridať 1 až k/2 rozsvietených žiaroviek.
Ďalej si ukážeme, že naše riešenie je optimálne. Náš algoritmus potrebuje i vypínačov pre 2i žiaroviek. Každý vypínač sa môže nachádzať v jednej z dvoch polôh, a to buď zapnutý, alebo vypnutý. S i vypínačmi môžeme popísať práve 2i rôznych stavov. Z rôzne „postláčaných“ vypínačov chceme získať rôzny počet rozsvietených žiaroviek. Ak by sme vypínačov mali len i-1, tak s nimi vieme dosiahnuť maximálne 2i-1 stavov. My ale potrebujeme 2i rôznych zasvietení (1 až 2i).
Pôvodná úloha
Na záver sa vrátime k pôvodnému zadaniu úlohy. Teda hľadáme riešenie pre ľubovoľný počet žiaroviek, nie len pre mocninou dvojky. No nezúfajme, naše predošlé riešenie sme nerobili zbytočne. Skupinu n žiaroviek si rozdelíme na dve časti. Prvá časť bude obsahovať našu Nádej a počet žiaroviek v tejto časti bude rovný najväčšej mocnine dvojky, ktorá je menšia alebo rovná n. Exponent tejto mocniny si označíme ako i.
Druhá časť bude obsahovať všetky zvyšné žiarovky a bude určite menšia ako tá prvá časť. Je to preto, lebo ak by bola druhá časť väčšia alebo rovná ako tá prvá, tak by sme potom mohli vziať väčšiu mocninu dvojky v prvej časti, než sme vzali. Prvú časť, ako sme dokázali v zjednodušenej úlohe, vieme najlepšie vyriešiť s i vypínačmi. Celú druhú časť pripojíme na jeden spoločný vypínač. Prvými i vypínačmi vieme rozsvietiť 1 až 2i žiaroviek a posledným vypínačom zvyšok, teda n-2i žiaroviek. Ak chceme rozsvietiť viac ako 2i žiaroviek, stačí nám rozsvietiť druhú časť a k tomu doplňujúci počet žiaroviek z prvej časti.
Ešte potrebujeme ukázať, že potrebný počet vypínačov je najmenší možný. Pre n žiaroviek si nájdeme najbližšiu menšiu mocninu dvojky než n. Túto mocninu si označíme ako 2i. Následne využijeme podobnú úvahu, akú sme použili pri 2i žiarovkách. Ak by nám stačilo i vypínačov, tak vieme popísať 2i stavov. Pritom vieme, že 2i < n, teda potrebujeme najmenej i+1 vypínačov.