Matematická olympiáda – kategorie P
Řešení úloh ústředního kola (2. soutěžní den) 53. ročníku
P-III-4 Psíci
Na poskakování psíků se můžeme dívat jako na hru. Stav hry lze jednoznačně popsat pozicí obou psíků. Skok psíků představuje tah. Když oba psíci skočí, změní stav hry. Povolené stavy hry budou ty, které odpovídají povoleným pozicím psíků. Pro každý stav hry budeme zkoumat, kolika tahy se do něho dá dostat z počátečního stavu (když jsou oba psíci na výchozích místech). Tento počet tahů budeme označovat jako vzdálenost daného stavu.Vzdálenost počátečního stavu je 0. Všechny stavy, do nichž se lze z něho dostat jedním tahem, budou ve vzdálenosti 1. Nyní projdeme všechny stavy ve vzdálenosti 1 a hledáme, do kterých nových stavů se z nich dostaneme - ty budou zjevně ve vzdálenosti 2. Takto můžeme analogicky pokračovat pro stavy ve vzdálenosti 3, 4, ... Skončíme, když najdeme koncový stav (oba psíci jsou na svých cílových místech), nebo když už nenajdeme žádný nový stav. Tato technika prohledávání stavů se nazývá prohledávání do šířky.
Otázkou zůstává, jak pro každý stav určit, do kterých dalších (sousedních) stavů se z něho lze dostat jedním tahem. Pomohlo by nám, kdybychom uměli pro každé políčko na louce určit čísla jeho sousedů. Sousední stavy bychom potom určili snadno. Ze všech možných pohybů oběma psíky 6 směry (36 možností) vyškrtáme skákání stejným směrem, skákání na bodláky, skok některého psíka mimo louku a současný skok obou psíků na totéž políčko.
Abychom našli sousední políčka snadněji, ukážeme si, jak se dá šestiúhelníkový plán louky reprezentovat v obyčejném dvojrozměrném poli. Na políčku 1 si zvolíme dva směry. Jeden určuje rostoucí směr první souřadnice, druhý směr druhé souřadnice. Takto jsme přiřadili každému políčku souřadnice x, y, kterým odpovídají indexy v obyčejném dvojrozměrném poli. V dvojrozměrném poli je už nalezení sousedů lehké. Konkrétně při naší volbě souřadnicových os budou mít sousedi políčka (x,y) souřadnice (x,y+1), (x-1, y), (x-1, y-1), (x, y-1), (x+1, y) a (x+1, y+1).
Jak zjistíme pro políčko s číslem k jeho souřadnice? Všimněte si, že spirálu
můžeme rozložit na vrstvy šestiúhelníkového tvaru. Nejprve
určíme, na kolikáté vrstvě spirály se k nachází, potom stranu na této vrstvě,
pozici políčka na straně a je to.
Nultá vrstva spirály obsahuje 1 políčko, i-tá vrstva pak 6i, jelikož každá vrstva má 6 stran a na každé straně je i políček. Celkový počet políček ve spirálách 0...v je tedy 1+(6*1+...+6*v) = 3v2+3v+1.
A jak zjistíme, kde se nachází políčko k? Nejdříve spočteme vrstvu - najdeme kladné řešení rovnice k=3v2+3v+1 a zaokrouhlíme ho nahoru. Po vyřešení dostaneme v=[-1/2+(k/3-1/12)1/2]. (Jednodušší a trochu pomalejší postup: zvyšujeme v, dokud počet políček nedosáhne k.)
Když už víme vrstvu v, kde se políčko nachází, pořadové číslo políčka ve vrstvě (číslováno od 0) dopočítáme snadno: odečteme od k celkový počet políček na dřívějších vrstvách a ještě 1. Na vrstvě v má každá strana v políček, rozdíl tedy stačí vydělit v. Číslo strany s bude podíl, pozice na straně p bude zbytek po tomto dělení.
Již umíme pro dané políčko k spočítat jeho vrstvu v, stranu s a pozici
na straně p. Z těchto hodnot dostaneme souřadnice podle následující tabulky (platí pro v>=1):
s x y 0 +v-1-p +v 1 -1-p +v-1-p 2 -v -1-p 3 -v+1+p -v 4 +1+p -v+1+p 5 +v +1+p
Implementace
Stav hry je jednoznačně reprezentován souřadnicemi x1, y1, x2, y2 obou psíků. Při prohledávání do šířky si pamatujeme seznam stavů, které jsme již dosáhli, ale ještě jsme z nich nezkoušeli prohledávat nové vrcholy. K tomu nám poslouží fronta. Dále potřebujeme umět pro každý stav rychle zjistit, zda jsme ho ještě neviděli, už viděli, nebo zda se do něj nedá jít (bodláky). K tomu používáme čtyřrozměrné pole, kde je to přímo zapsáno. (Přesně totéž se dalo reprezentovat dvojrozměrným polem, které bychom indexovali původními souřadnicemi. Navíc bychom ale potřebovali umět ze souřadnic určit původní číslo políčka.)Abychom nemuseli při prohledávání do šířky stále kontrolovat, zda se nedostaneme ven z louky, postavíme okolo celé louky bodláky. Zakážeme také stavy, v nichž by byli oba psíci na stejném místě.
Časová i paměťová složitost prohledávání je lineární vzhledem k velikosti tohoto prostoru, tedy O(N2).
P-III-5 AttoSoft
Označme S=l1+...+lN počet dní, které AttoSoft potřebuje na dokončení všech programů. Poslední program tedy dokončíme po S dnech.Pro každý program spočítáme pokutu, kterou bychom za něj zaplatili, kdybychom ho dokončili až po S dnech. Program s nejmenší takovou pokutou zařadíme do rozvrhu jako poslední. Je-li to program číslo i, zbývá nám naplánovat všechny zbývající programy na prvních S-li dní, což provedeme stejným způsobem (tzn. opět vybereme jako poslední program s nejnižší pokutou po S-li dnech, atd.)
Správnost uvedeného algoritmu dokážeme indukcí vzhledem k počtu programů, které potřebujeme dokončit. Pokud je třeba dokončit jeden program, existuje jen jediný možný rozvrh, a náš algoritmus tedy funguje jistě správně.
Nechť tedy počet programů, které je třeba dokončit, je N a nechť pro libovolný menší počet programů náš algoritmus funguje správně. Označme G řešení získané naším algoritmem (v tomto řešení je posledním programem program číslo i). Nechť existuje jiné, levnější řešení O, které končí programem číslo j. Jestliže i=j, pak rozdíl mezi G a O musí být v pořadí prvních N-1 programů. Podle indukčního předpokladu však toto pořadí v řešení G je optimální, proto řešení O nemůže být levnější.
V opačném případě vytvoříme nový rozvrh O' následujícím způsobem. Nechť rozvrh O dokončuje programy v pořadí o1,o2,...,oN a nechť ok=i. Podle rozvrhu O' dokončíme programy v následujícím pořadí: o1,o2,...,ok-1,ok+1,...,oN,i. Všimněte si, že řešení O' je nejvýše tak drahé, jako řešení O. Pokuta za programy ok+1,...,oN je totiž nižší než v řešení O, neboť je dokončíme dříve (pokuta roste s počtem dní po termínu). Navíc pokuta za program i dokončený po S dnech určitě nepřesahuje pokutu za program oN dokončený po S dnech, jelikož program i jsme vybrali tak, aby tato pokuta byla nejmenší možná.
Řešení O' ale nemůže být levnější než řešení G (platí tu stejný argument, jako v předchozím případě). Proto ani řešení O nemůže být levnější než G. Dokázali jsme, že žádné levnější řešení než G neexistuje, řešení určené naším algoritmem je tedy optimální.
V každém kroku algoritmu musíme spočítat příslušnou pokutu pro každý program, který jsme dosud nezařadili do rozvrhu. Proto časová složitost algoritmu je O(N2).
Při výpočtu si ještě musíme dávat pozor na to, že pokuta může být až 5 000 * 100 0003 + 5 000 * 100 0002 + ... + 5 000, tedy přibližně 5 * 1018, a tak velké číslo se již nevejde do longintu a nemůžeme si dovolit použít ani typ real, jelikož potřebujeme i u tak velkých čísel rozlišovat rozdíly na řádu jednotek, Většina překladačů naštěstí nabízí 64-bitový celočíselný typ - v Turbo Pascalu je to typ comp, ve Free Pascalu například typ QWord.