Druhá 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-Z2-1 Stánkař (Zadání)
Co je na úloze se stánkařem a jeho nedočkavými zákazníky hezké, je to, že jde řešit několika různými jednoduchými způsoby, a ač to všechno budou simulace („přehrajeme si“, co se u stánku bude dít), tak podstatou vycházejí z různých myšlenek.
Prvním způsobem, který vám chceme předvést, je simulace podle času. Pořídíme si cyklus, ve kterém budeme skákat po celých minutách od času 0 dál a při tom budeme zkoumat, co se v ten čas děje se zákazníky (mohli bychom tento postup nazvat i více matematicky iterací podle času).
Zákazníky si můžeme na začátku načíst do pole (abychom se mohli průběžně dívat na čas dalšího zákazníka a porovnávat ho s časem simulace) a současně si budeme v jiném poli držet frontu zákazníků stojících u stánku. V každém kroku simulace potřebujeme:
- Přidat do fronty zákazníky, kteří přišli v tento čas,
- odstranit z fronty všechny zákazníky, kteří již čekali příliš dlouho a odešli,
- obsloužit jednoho zákazníka (pokud je fronta zákazníků u stánku neprázdná),
- zvednout čas o 1 a pokračovat v dalším kroku simulace.
Při programování simulace je dobré si rozmyslet, kdy chceme simulaci ukončit a vydat výsledek. V našem případě to bude, když už nám nebudou zbývat žádní zákazníci (ani v poli zákazníků, ani ve frontě).
Taková simulace se dá naprogramovat celkem jednoduše a na naši úlohu s přehledem stačí. Problém by ale mohla mít ve chvíli, kdyby mezi zákazníky byly obrovské mezery a simulace by musela udělat miliony kroků „naprázdno“.
Druhým způsobem, který ukážeme, je simulace iterující přes zákazníky. Jak už její název napovídá, tak nebude „skákat“ po jednotlivých minutách a během toho obsluhovat zákazníky, ale bude „skákat“ po zákaznících a během toho kontrolovat čas.
Bude nám stačit držet si nejdřívější čas, ve kterém můžeme obsloužit dalšího zákazníka (což na začátku bude čas 0). Pak v každém kroku simulace načteme dalšího zákazníka v pořadí. Pokud bude nejbližší čas obsloužení dalšího zákazníka…
- …dříve, než přijde tento zákazník ke stánku, tak ho určitě zvládneme obsloužit a nejdřívější čas obsloužení dalšího zákazníka nastavíme na minutu po příchodu tohoto.
- …méně než 10 minut po příchodu tohoto zákazníka, tak ho také stihneme obsloužit a nejdřívější čas obsloužení dalšího zákazníka zvedneme o jednu minutu.
- …větší nebo rovno 10 minutám po příchodu tohoto zákazníka, tak ho obsloužit nezvládneme, zákazník odejde z fronty a my budeme pokračovat s dalším zákazníkem.
Toto řešení má o něco složitější myšlenku, na implementaci je však jednodušší, než to první. Stále se jedná o simulaci, ale už mu nebudou dělat problémy velké mezery (a zvládne tak vždy odpovědět v lineárním čase vzhledem k velikosti vstupu.
Program (Python 3 – simulace podle času)
Program (Python 3 – iterace přes zákazníky)
33-Z2-2 Kulinářský hlavolam (Zadání)
Pojďme nejprve rozmyslet přímočaré řešení – vyzkoušíme všechny možnosti, jak rozestavět hrnce na plotýnky, a z nich vybereme tu, která splňuje všechny požadavky. Takový přístup jistě funguje, ale samotných rozestavění je až N!, což už je příliš. A to ani neuvažujeme čas potřebný k ověření validity rozestavění.
Nemůžeme to nějak zrychlit? Pro každý hrnec je přece snadné určit všechny plotýnky, na kterých stát nesmí – to jsou ty menší než on sám a ty, na kterých už nějaký hrnec stojí. Jak si ale vybrat, na kterou použitelnou plotýnku hrnec umístit, aby nám tam později nepřekážel? Snadno, nalezneme nejmenší, která postačuje. Hrnce, které jsou větší než ploténka, by na ni stejně nepasovaly a těm menším jsme zase nijak neuškodili – ty lze postavit i na jakoukoli větší. Nápad můžeme také převrátit a ke každé plotýnce hledat co největší hrnec, který se na ni vejde.
Jak dlouho běží tento algoritmus? Pro každý hrnec zkusíme projít všechny plotýnky (nebo naopak), na což potřebujeme O(NK) kroků. To je mnohem lepší než naše původní řešení, ale stále může být příliš pomalé pro dlouhé vstupy.
Pojďme zrychlit tu variantu, kdy na každou plotýnku stavíme největší možný hrnec. Hrozně moc času strávíme hledáním správného hrnce. To je pochopitelné, když přicházejí plotýnky libovolně. Ani pořadí, ve kterém vybíráme hrnce, nemá moc řád, ale s tím se dá něco dělat. Pojďme si seřadit plotýnky od největší k nejmenší a v tom pořadí je procházet. Teď už vždy hledáme největší hrnec velikostí menší roven předchozímu. Ale protože předchozí jsme už použili, je to vlastně vždy největší nepoužitý hrnec.
Jak toho využít? Seřaďme si i hrnce od největšího k nejmenšímu. Teď už je řešení snadné. Vezměme vždy první hrnec, postavme jej na první plotýnku a následně oba odeberme (nebo prostě přeskočme). Pokud náhodou narazíme na dvojici, která na sebe nepasuje, víme, že to určitě ani jinak nejde a úloha nemá řešení. Takový případ nám dokonce zadání nepovoluje.
Jak dlouho to nakonec trvá? Nejrychlejší řadící algoritmy, které známe a dají se použít na čísla libovolného rozsahu, zaberou O(N log N) času. Podrobnosti lze najít např. v naší kuchařce. V našem případě to udělá O(N log N + K log H), což, protože K je nejvýše N, odpovídá O(N log N).
33-Z2-3 Rostoucí funkce (Zadání)
Představme si, jak bychom tento problém řešili ručně, bez počítače. Můžeme si prostě tipnout nějaké číslo x a spočítat si funkční hodnotu f(x) v tomto bodě. Pokud bude hledaný výsledek větší než toto f(x), musíme x trochu zvýšit. Stejně tak i naopak, pokud jsme výsledek přestřelili, musíme si tipnout menší x. Tento postup samozřejmě funguje jen v případě, že je funkce rostoucí. To však máme v zadání slíbeno.
Podle čeho se budeme rozhodovat, jaké x si tipnout? Na začátku máme dolní odhad 1 a horní odhad 100. Zkusme si tipnout x uprostřed tohoto úseku. Tento střed spočítáme jako aritmetický průměr obou odhadů. Pokud zjistíme, že hledaná hodnota je větší než f(x), víme, že x musí být větší než střed. Díky tomu můžeme použít tento střed jako svůj vylepšený dolní odhad. Obdobně, pokud by byla hledaná hodnota menší než f(x), použijeme střed jako nový horní odhad.
Tento krok opakujeme a postupně vylepšujeme své dolní a horní odhady. Můžeme si všimnout, že při každém kroku se rozdíl mezi nimi zmenší na polovinu. Díky tomu budou naše tipy přesnější a přesnější. Jakmile si tipneme takové x, že se f(x) od hledané hodnoty liší o méně než setinu, máme vyhráno.
Pozor na to, že zaokrouhlujeme pouze f(x). Samotné x zaokrouhlovat nesmíme, protože jej mnohdy potřebujeme určit přesněji. Hodnota f(x) se totiž může změnit o více než jednu setinu i v případě, že se x změní jen maličko. Pro polynom z úlohy například platí f(25) = 50780 a f(25.0001) ≐50780.67.
Zmíněnému přístupu se říká binární vyhledávání. Lze jej použít, pokud vstup vždy roste nebo klesá – například k hledání v setříděném poli. Jeho časová složitost je logaritmická vzhledem k rozsahu čísel, který musíme prohledat.
Výše zmíněné řešení bylo naprosto dostačující. Ještě ale nastíníme jedno možné vylepšení: Při ručním hledání máme určitý pojem o tom, jak blízko výsledku jsme. Pokud vyšel dolní odhad jenom trochu mimo, zatímco horní odhad je od výsledku daleko, bylo by lepší zkoušet tipovat čísla blíže dolnímu odhadu. Jak tohle říct programu? Využijeme lineární interpolace. To znamená, že si představíme, že mezi oběma odhady má funkce podobu úsečky. Pro úsečku, respektive přímku, už umíme k dané hodnotě zpětně dopočítat x. Takto spočítané x použijeme jako nový tip. Bohužel, pro některé funkce by tento postup mohl být příliš pomalý, proto se vyplatí střídat takovéto tipy a dělení úseku napůl pomocí binárního vyhledávání.
33-Z2-4 Měření plachty (Zadání)
Pro každé dva stěžně je plocha plachty mezi nimi jednoznačná. Zkusme nejdříve nastavit levý i pravý stěžeň na ty krajní a uložme si je jako zatím nejlepší řešení. Vzdálenost mezi nimi je největší možná, takže najdeme-li větší plachtu, bude určitě vyšší. Proto vyšší ze stěžňů ponechme a posuňme se směrem k němu od toho nižšího (pokud mají oba stejnou výšku, můžeme klidně posunout obě pozice). Argument o zvyšování plachty stále funguje a proto můžeme tento krok opakovat. Pokaždé přitom změníme záznam nejlepšího řešení, pokud jsme našli lepší.
Jakmile má náš levý stěžeň stejnou pozici jako pravý, skončíme a vrátíme uložené nejlepší řešení. Díky našemu argumentu přitom máme jistotu, že jsme nezanedbali lepší možnost.
V každém kroce jen zjistíme plochu, která odpovídá aktuálním pozicím stěžňů, a porovnáme ji s dosud nejlepším výsledkem, což trvá konstantní čas. Vzdálenost mezi stěžni se přitom mezi kroky vždy o jedna sníží, kroků tak nebude více, než je stěžňů. Algoritmus tedy poběží lineárně dlouho vůči velikosti vstupu.