Třetí 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-Z3-1 Šikmá věž z krabic (Zadání)
Nejprve je důležité si rozmyslet, jakým způsobem chceme krabice na sebe lepit, abychom maximalizovali celkovou šířku šikmé věže. Protože nám na výšce věže nezáleží, chceme každou krabici otočit „na šířku“ (delším rozměrem vodorovně). Zároveň musíme krabici umístit tak, aby její těžiště leželo na předchozí krabici. Těžiště se nachází právě v polovině šířky krabice, a tudíž když chceme krabici co nejvíce využít, položíme ji těžištěm na hranu předchozí krabice. Z toho plyne, že kromě první krabice každá krabice přispívá k celkové šířce věže polovinou své delší strany. Zůstává otázka, jak vybrat první krabici. Protože první krabice přispívá k věži celou svou délkou, chceme jako první umístit tu nejširší krabici. Na pořadí ostatních krabic nezáleží.
Jak tedy bude Kevin postupovat? Nejprve vybere krabici s nejdelší stranou a přilepí ji na zem. Další krabice bude brát v pořadí tak, jak mu přijdou pod ruku. Vždy je otočí na šířku a nalepí je těžištěm na pravý kraj předchozí krabice.
Protože Kevin s každou krabicí interaguje nejvýše dvakrát, časová složitost algoritmu bude lineární vzhledem k počtu krabic.
33-Z3-2 Přečasování titulků (Zadání)
Jak zmiňuje zadání, titulky se od filmu liší rychlostí a jsou posunuté. Kdybychom obě informace znali, můžeme titulky snadno opravit – každou časovou značku nejprve vynásobíme koeficientem zrychlení a poté přičteme posun.
| délka(titulky) |
| délka(film) |
Jakmile známe koeficient, přenásobíme s ním časy titulků a zbývá určit posun. To už je ale snadné. Časy obou Kevinem nalezených titulků jsme již opravili z hlediska rychlosti, takže rozdíl mezi Kevinovým časem a časem po přenásobení koeficientem je hledaný posun.
Pozorování výše už snadno přetavíme v algoritmus. Načteme oba Kevinem identifikované titulky a pak všechny titulky. Přitom se v nich snažíme odhalit identifikované repliky (ty jsou naštěstí unikátní). S optimalizací porovnávání řetězců si těžkou hlavu dělat nemusíme – provedeme pouze konstantně (2) porovnání s každým titulkovým textem. Jakmile najdeme odpovídající si páry, provedeme již známý výpočet a znovu projdeme přes titulky a každý opravíme.
Časová složitost je lineární vzhledem k velikosti vstupu a paměťová taktéž.
33-Z3-3 Chamtivý stánkař (Zadání)
V řešení této úlohy budeme vycházet z řešení úlohy v minulé sérii. Tam jsme řešili podobný problém s jediným rozdílem, že nyní jsme přidali druhý druh nápoje (či vlastně zákazníka) a priority ve zpracování.
Jedním z ukazovaných řešení u minulé úlohy byla iterace podle času. Stejnou myšlenku můžeme zopakovat i u této úlohy. Akorát si musíme pořídit dvě fronty. Další postup můžeme odvozovat za pomoci představy, že běží čas a stánkař se v každý okamžik nějak rozhoduje. Události můžeme popsat například takto:
- Noví lidé si stoupnou do správných front.
- Dlouho čekající lidé fronty opustí.
- Pokud je ve frontě na čaj nějaký zákazník, bude obsloužen.
- Pokud je ve frontě na limo nějaký zákazník a zároveň nebyl obsloužen nikdo s čajem, bude podána limonáda.
- Posuneme čas o minutu dopředu.
Můžeme si rozmyslet, že tento popis událostí zhruba odpovídá tomu, co by se ve zjednodušeném světě u stánku dělo. Implementace řešení pak může tento postup doslovně sledovat. Podobně jako v minulé úloze bude řešení dostačující, ale relativně pomalé. Jak bychom tedy mohli implementaci zjednodušit a zrychlit?
Reálně to zas tak moc nejde. Žádný z kroků simulace nemůžeme odstranit, protože pak bychom počítali něco jiného. Můžeme je akorát přesouvat jinam, či je zkusit jednotlivě zrychlit.
Jedním takovým vylepšením je pozorování, že první krok vlastně nepotřebujeme. Je to kus kódu, který přehazuje načtený vstup prakticky ve stejném formátu do dvou front. Kdybychom vstup do front načetli přímo, můžeme se ve zbytku programu tvářit, že v nich „zákazníky z budoucnosti“ nevidíme. Touto relativně jednoduchou změnou si sice zásadně nepomůžeme v rychlosti programu, ale zbavíme se zbytečné duplicity.
Druhé pozorování se týká hodin. Kdybychom přičítali pouze jedničku, tak se nám může stát, že spoustu času trávíme děláním ničeho. Kdybychom ale nějak věděli, na jaký čas v budoucnu skočit, tak bychom se prodlevám vyhnuli. Díky předchozí změně to ale přeci víme! V obou frontách jsou „zákazníci z budoucnosti“. Stačí se tedy podívat, kdy přijde první z nich a na tento čas přímo skočit. Tím vlastně způsobíme, že vnější cyklus simulace poběží nejvýše tolikrát, kolik je zákazníků na vstupu. Předtím to bylo za každou minutu jednou.
Co jsme poslední změnou získali? Můžeme se ohlédnout zpět na druhé řešení minulé úlohy, kterému jsme říkali iterace přes zákazníky. Vlastně jsme teď vyrobili řešení, které se chová velmi podobně. Sice iteruje přes čas, ale skáče pouze do okamžiků, kdy je potřeba nějakého zákazníka zpracovat. Formálně jsme složitost převedli z lineární v čase na lineární v počtu zákazníků. To znamená, že už počet kroků algoritmu neovlivňuje čas, kdy zákazníci přicházejí.
Kdybychom chtěli podobné řešení napsat od začátku jako iteraci přes zákazníky, mohli bychom samozřejmě také. Myšlenka je to ale o něco málo komplikovanější a ničím nám proti řešení výše nepomůže. Nebudeme ji tedy zde rozebírat. Můžete si ji tak aspoň rozmyslet jako cvičení…
33-Z3-4 Statek (Zadání)
Přímočaré řešení je takové, že zkusíme postavit statek postupně na každém z políček a vždy zjistíme, jak velká jsou pole kolem něj. Průběžně si pamatujeme, pro které umístění statku byla tato plocha polí největší. Jakmile vyzkoušíme všechna políčka, budeme znát optimální umístění.
Jak ale spočítáme velikost polí kolem statku? Z políčka se statkem spustíme prohledávání do šířky. Najdeme všechna políčka polí, se kterými statek přímo sousedí. Poté najdeme jejich sousední políčka, a tak dále, dokud nenajdeme všechna políčka, na která lze ze statku kombajnem dojet. Políčka průběžně počítáme, musíme si však dát pozor, abychom některé nezapočítali vícekrát, ta již započítaná si proto budeme označovat.
Bude-li počet políček N, z každého políčka můžeme prohledat až celou mapu. Časová složitost proto bude O(N2).
To samé prohledávání děláme několikrát, pojďme to vylepšit. Jednotlivé plochy polí si od sebe odlišíme a pro každé políčko si budeme pamatovat, jakého pole je součástí a jak je toto pole velké. Uděláme to tak, že postupně projdeme všechna políčka polí, a pokud u daného políčka ještě nevíme, do jakého pole patří, spustíme z něj nové prohledávání a tím si všechna políčka v tomto novém poli označíme.
Dále můžeme postupovat stejně jako v přímočarém řešení, ovšem nyní dokážeme velikost polí kolem statku spočítat okamžitě. Podíváme se na čtyři sousední políčka a zjistíme, do jakých polí patří. Velikosti těchto polí sečteme, ale nesmíme totéž pole započítat vícekrát. Proto jsme si u každého políčka kromě velikosti pamatovali i to, do jakého pole patří.
Toto řešení již běží v čase O(N). Musíme ukládat informace pro daná políčka, paměťová složitost tedy bude také lineární.