======== HW04 Dynamické programování ======== {{:courses:b6b36dsa:ukoly:dprg.png?300 |}} Stavební firma projektuje a staví lanovky v horách. Lanovky jsou určené převážně na zimní provoz, vozí lyžaře. Ti se pak spouští z kopců po sjezdovkách nebo i volně terénem. Stavební firma dostane od zadavatele mapu kopce, na kterém má být lanovka postavena. Mapa je dána jako dvourozměrná matice velikosti $n \times m$ nadmořských výšek $a_{ij}, 1 ≤ i ≤ n, 1 ≤ j ≤ m$ jednotlivých bodů v terénu. Zadání je naprojektovat **lanovku** vedoucí přes kopec tak, aby její provoz byl minimální, tj. aby po své trase zbytečně neztrácela nadmořskou výšku a aby její celková délka byla minimální. Současně má firma navrhnout optimální **trasy sjezdovek**, které vzniknou na cestách vybudovaných pro výstavbu lanovek. Po cestách se bude vozit těžká technika, proto trasa opět nesmí zbytečně ztrácet výšku a vede delšími cestami v serpentinách. Tyto vlastnosti uvítají i lyžaři, kteří budou cesty využívat pro sjezd. Po mapě se lze pohybovat pouze vlevo, vpravo, nahoru nebo dolů, vždy na následující prvek pole. Pohyb po diagonále možný není. **Cesta přes kopec** je definována jako posloupnost nadmořských výšek bodů $v_1,v_2,…,v_k$, kde $v_1 = a_{1, 1}$ a $v_k = a_{n, m}$. Současně existuje index $z$, $1 ≤ z ≤ k$ takový, že platí $v_1<⋯⋯>v_k$. Snahou je, aby hodnota nadmořské výšky $v_z$ byla maximální možná. Nejvyšší bod mapy může být umístěn v kráteru a nemusí být proto podle definice dosažitelný. Maximalizace výšky má při řešení úlohy nejvyšší prioritu - viz [[courses:b6b36dsa:ukoly:hw04#priklad_7_kopec_1_07|příklad 7]]. **Stoupání**, resp. **klesání** cesty je definováno jako $S_u = \mathop{\text{max}} \{ | v_{i} - v_{i - 1} |, 1 < i ≤ z \}$, resp. $S_d = \mathop{\text{max}} \{ | v_{i} - v_{i - 1} |, z < i ≤ k \}$. Sklon cesty přes kopec definujeme jako maximum stoupání a klesání cesty - $S = \mathop{\text{max}} \left( S_u, S_d \right)$. **Lanovka** (lift) vyžaduje nejkratší cestu přes kopec, která má maximální sklon, tj. ze všech nejkratších cest hledáme tu, která má maximální sklon. Délka cesty je dána rozměry matice a je rovna $n - 1 + m - 1 = n + m - 2$. **Sjezdovka** (piste) je vedena nejdelšími cestami přes kopec s minimalizací sklonu cesty (s minimalizací maximálního sklonu svahu), tj. ze všech nejdelších cest hledáme tu, která má minimální sklon $S$. Na úvodním obrázku je vidět cestu pro lanovku (znázorněno hnědě) a cestu vedoucí v serpentinách pro sjezdovku (znázorněno oranžově). Pokud existují dvě různé cesty, vybíráme tu, která: - je nejkratší (lanovka), resp. nejdelší (sjezdovka), - vede nejvýš, - sklon cesty je maximální (lanovka), resp. minimální (sjezdovka), současně se snažíme o maximalizaci/minimalizaci stoupání i klesání cesty. **Řešení úlohy může být i více** Viz [[courses:b6b36dsa:ukoly:hw04#priklad_3_kopec_1_03|příklad 3 (lift)]]. Pokud je víc stejných řešení úlohy, jsou všechna řešení vyhodnocovacím skriptem vyhodnocena jako správná. Vyhodnocení probíhá v několika krocích: - je zkonstrolováno, že cesta je cestou na zadané mapě podle definice, - je zkontrolováno, že cesta nejprve stoupá a pak klesá - má pouze jedno maximum a žádné dva body vedle sebe nemají stejnou nadmořskou výšku, - s referenčním řešením je srovnávána délka (length) cesty, která musí být "lepší nebo stejná" jako délka cesty nalezená referenčním řešením, - s referenčním řešením je konfrontováno stoupání cesty (gradient) podle definice. Lanovka i sjezdovka může částečně nebo i úplně vést po stejných cestách. ====== Vstup a výstup programu ====== Na vstupu (čteme ze standardního vstupu) je dvourozměrná matice nadmořských výšek jednotlivých bodů v terénu. Na prvním řádku vstupu jsou dvě čísla ''n'' a ''m'' – rozměry matice. Následuje ''n'' řádků s ''m'' hodnotami – jednotlivé prvky matice. Pokud při čtení vstupu zjistíte chybu, vypište na standardní chybový výstup zprávu ''Error: Chybny vstup!'' a program ukončete s návratovou hodnotou ''1''. Program může mít jeden z argumentů: * ''lift'' – pro vyhledání cesty pro lanovku, * ''piste'' – pro vyhledání cesty pro sjezdovku. Pokud program argument nemá, vyhledá cestu pro lanovku i sjezdovku, postupně za sebou. Pro každou nalezenou cestu je výsledek vypsán na dvou řádcích: * délka cesty $k$, * posloupnost $v_1,v_2,…,v_k$ nadmořských výšek bodů cesty. Pokud cesta na mapě neexistuje, vypíšte na standardní chybový výstup zprávu ''Error: Cesta neexistuje!'' a program ukončete s návratovou hodnotou ''1''. ====== Algoritmus řešení úlohy ====== Je zřejmé, že pro řešení úlohy je potřeba prohledat mapu do šířky. S využitím rekurze to může být s ohledem na hloubku rekurze problém. Proto se zde uplatní dynamické programování a princip memoizace, kdy si jednou vypočtené údaje pamatujeme a nepočítáme je opakovaně. V úloze je zadána matice nadmořských výšek. Pokud vypočteme cestu pro lanovku (sjezdovku) do nějakého bodu, tuto informaci je dobré si pamatovat. K tomu využijeme dvourozměrné pole. Přemýšlejme nejprve, jaké údaje je nutné si pamatovat: * délku cesty do daného bodu, * maximální/minimální sklon cesty do daného bodu, * předchůdce daného bodu - cestu budeme muset zpětně rekonstruovat. Podle postupu řešení může být dobré si pamatovat i více údajů. **Jakým způsobem budeme jednotlivé prvky matice počítat?** Zde je dobré si uvědomit, která "políčka" dvourozměrného pole mohou ovlivnit výsledek na místě (indexu) $[i][j]$ (i je číslo řádku, j číslo sloupce). Při hledání cesty **pro lanovku** lze zjistit, že pro výpočet hodnot na místě $[i][j]$ v dvourozměrném poli je potřeba znát hodnoty na indexech $[i - 1][j]$ a $[i][j - 1]$. Situaci si nakreslete a přemýšlejte, jak to ideálně zařídit, abychom při výpočtu hodnoty $[i][j]$ znali hodnoty, které potřebujeme. Při hledání cesty **pro sjezdovku** je situace obtížnější. Výpočet hodnoty na místě $[i][j]$ se může měnit až do doby, dokud nejsou vypočteny všechny okolní hodnoty $[i - 1][j]$, $[i + 1][j]$, $[i][j - 1]$, $[i][j + 1]$. Tak by ale výpočet mohl běžet do nekonečna. Je proto dobré si uvědomit několik skutečností: * Nemusíme nutně prohledávat všechny čtyři směry, stačí prohledávat ty, z nichž se do bodu $[i][j]$ dostaneme z bodu s nižší nadmořskou výškou. * Body, které se mohou průběžně měnit, je vhodné si pamatovat, například ve frontě. **Jak ovlivní předchozí "políčka" dvourozměrného pole hodnotu na místě (indexu) $[i][j]$?** Při hledání cesty **pro lanovku** se délka cesty se při přechodu z políčka $[i - 1][j]$, resp. $[i][j - 1]$ na políčko $[i][j]$ zvýší o jedničku. Sklon cesty upravíme podle aktuální hodnoty sklonu na políčkách $[i - 1][j]$ a $[i][j - 1]$ a sklonů mezi body $[i - 1][j]$, resp. $[i][j - 1]$ a $[i][j]$. Při výpočtu respektujeme hlavní princip dynamického programování - dílčí problémy řešíme samostatně (lokálně) podle aktuální situace. Požadavek zadání na délku cesty a její sklon nelze proto řešit globálně - nad celou mapou. Požadavky zahrneme pouze do lokálních rozhodnutí o dalším postupu v cestě. Při hledání cesty **pro sjezdovku** postupujeme obdobně, akorát musíme projít všechny sousedy bodu $[i, j]$, tj. body $[i - 1][j]$, $[i][j - 1]$, $[i + 1][j]$ a $[i][j + 1]$. Jejich parametry se v průběhu výpočtu mohou měnit, indikaci změny je vhodné si pamatovat, například ukládáním bodů do fronty. Hledání cesty z kopce je problém obdobný problému hledání cesty do kopce - po prohození počátečního a koncového bodu cesty. Výslednou délku cesty a nejvyšší bod zahrneme do výpočtu až po vyřešení problému hledání cesty do a z kopce. Až si úlohu dobře promyslíte a přesto si s řešením nebudete vědět rady, doporučujeme podívat se na [[https://cw.fel.cvut.cz/wiki/courses/b6b36dsa/ukoly/hw04#dodatek_k_postupu_reseni|Dodatek k postupu řešení]]. ===== Rozdíl v cestě pro lanovku a sjezdovku ===== **Délka cesty** Na mapě rozměrů $3 \times 3$ lze vidět rozdíl v cestě pro lanovku (obrázek vlevo) a sjezdovku (obrázek vpravo). Modré šipky znázorňují cestu nahoru, červené cestu dolů. {{:courses:b6b36dsa:ukoly:lanovka.png?200|}} {{:courses:b6b36dsa:ukoly:sjezdovka.png?200|}} Optimální cesta pro lanovku má délku $5$ a vede přes vrcholy ''1 8 9 6 5''. Možná je i varianta ''1 2 9 6 5'', protože stoupaní na obou cestách je stejné - první případ $8 - 1 = 7$, druhý případ $9 - 2 = 7$. Cesta pro sjezdovku se točí kolem celého kopce, její délka je $13$ a vede postupně přes vrcholy ''1 2 3 4 5 6 7 8 9 8 7 6 5''. **Nejvyšší bod cesty** Na mapě rozměrů $5 \times 4$ lze opět vidět rozdíl v cestě pro lanovku (obrázek vlevo) a sjezdovku (obrázek vpravo). Pokud cesta pro lanovku vede nejvyšším bodem, cesta pro sjezdovku se snaží být co nejdelší, a proto nejvyšší bod s výškou $20$ obchází. {{:courses:b6b36dsa:ukoly:lift1.png?200|}} {{:courses:b6b36dsa:ukoly:piste1.png?200|}} Nakonec ani lanovkou se nemusíme dostat na nejvyšší bod mapy (nadmořská výška $200$), pokud by daná cesta přes nejvyšší bod vůbec neexistovala. {{:courses:b6b36dsa:ukoly:lift2.png?400|}} {{:courses:b6b36dsa:ukoly:piste2.png?400|}} Testovací soubory z obrázků najdete {{ :courses:b6b36dsa:ukoly:test_hw04.zip |zde}}. ====== Kontrolní testy ====== Testovací soubory najdete {{ :courses:b6b36dsa:ukoly:dsa_hw04.zip |zde}}. ===== Miniaturní kopce velikosti $3 \times 3$ ===== ==== Příklad 1 – kopec_1_01 ==== Jediná neustále stoupající cesta na kopec. Všechny ostatní cesty vedou po rovině (1 1 nebo 2 2). ^ Vstup (stdin) ^ Výstup (stdout) lift ^ Výstup (stdout) piste ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | 3 3 1 2 3 1 2 4 1 2 5 | 5 1 2 3 4 5 | 5 1 2 3 4 5 | žádný | 0 | ==== Příklad 2 – kopec_1_02 ==== ^ Vstup (stdin) ^ Výstup (stdout) lift ^ Výstup (stdout) piste ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | 3 3 1 2 3 2 3 4 3 4 5 | 5 1 2 3 4 5 | 5 1 2 3 4 5 | žádný | 0 | ==== Příklad 3 – kopec_1_03 ==== Pro sjezdovku je má cesta stoupání 1 a je nejdelší možná. ^ Vstup (stdin) ^ Výstup (stdout) lift ^ Výstup (stdout) piste ^ Chybový výstup ^ Návratová hodnota ^ | 3 3 1 2 3 6 5 4 7 8 9 | 5 1 6 7 8 9 nebo 5 1 2 3 4 9 | 9 1 2 3 4 5 6 7 8 9 | žádný | 0 | ==== Příklad 4 – kopec_1_04 ==== ^ Vstup (stdin) ^ Výstup - lift ^ Výstup - piste ^ Chybový výstup (stderr) ^ Návratová hodnota ^ | 3 3 1 2 3 6 5 7 8 9 | žádný | žádný | Error: Chybny vstup! | 1 | ==== Příklad 5 – kopec_1_05 ==== ^ Vstup (stdin) ^ Výstup - lift ^ Výstup - piste ^ Chybový výstup (stderr) ^ Návratová hodnota ^ | 3 3 1 2 3 6 5 5 5 5 7 8 9 | žádný | žádný | Error: Chybny vstup! | 1 | ==== Příklad 6 – kopec_1_06 ==== ^ Vstup (stdin) ^ Výstup (stdout) lift ^ Výstup (stdout) piste ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | 3 3 1 2 3 2 3 2 3 2 1 | 5 1 2 3 2 1 | 5 1 2 3 2 1 | žádný | 0 | ==== Příklad 7 – kopec_1_07 ==== Cesta je v obou případech vybrána proto, že vede nejvýš, do nejvyššího bodu. ^ Vstup (stdin) ^ Výstup (stdout) lift ^ Výstup (stdout) piste ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | 3 3 1 2 3 2 4 2 3 2 1 | 5 1 2 4 2 1 | 5 1 2 4 2 1 | žádný | 0 | ==== Příklad 8 – kopec_1_08 ==== Cesta pro lanovku má nejvyšší stoupání i klesání ( 5 - 2 = 3). Naopak cesta pro sjezdovku stoupání i klesání minimalizuje (stoupání i klesání je 2). ^ Vstup (stdin) ^ Výstup (stdout) lift ^ Výstup (stdout) piste ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | 3 3 1 3 5 2 5 3 4 2 1 | 5 1 2 5 2 1 | 5 1 3 5 3 1 | žádný | 0 | ==== Příklad 9 – kopec_1_09 ==== Cesta na mapě neexistuje. ^ Vstup (stdin) ^ Výstup (stdout) lift ^ Výstup (stdout) piste ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | 3 3 1 2 9 2 1 2 3 2 5 | žádný | žádný | Error: Cesta neexistuje! | 1 | ==== Příklad 10 – kopec_1_10 ==== ^ Vstup (stdin) ^ Výstup (stdout) lift ^ Výstup (stdout) piste ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | 3 3 1 2 7 4 3 8 5 6 9 | 5 1 2 3 8 9 nebo 5 1 2 7 8 9 | 7 1 2 3 4 5 6 9 | žádný | 0 | ===== Středně velké a velké kopce ===== ==== Příklad 11 – kopec_2_01 ==== ^ Vstup (stdin) ^ Výstup (stdout) lift ^ Výstup (stdout) piste ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | 3 4 1 2 3 3 2 6 3 2 3 4 2 1 | 6 1 2 6 3 2 1 | 8 1 2 3 4 6 4 2 1 | žádný | 0 | ==== Příklad 12 – kopec_2_02 ==== Cesta pro lanovku maximalizuje stoupání, které je v obou případech 3. Naopak cesta pro sjezdovku minimalizuje stoupání, které je nakonec 2. ^ Vstup (stdin) ^ Výstup (stdout) lift ^ Výstup (stdout) piste ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | 5 5 2 3 4 6 10 3 4 5 6 11 4 5 7 9 12 7 8 9 10 12 10 9 8 13 14 | 9 2 3 4 7 8 9 10 13 14 nebo 9 2 3 4 5 6 9 10 13 14 ... ale i další řešení s délkou 9 a stoupáním 3 | 9 2 3 4 5 7 9 10 12 14 Cesta délky 9 se stoupáním 2 | žádný | 0 | ==== Příklad 13 – kopec_2_03 ==== ^ Vstup (stdin) ^ Výstup (stdout) lift ^ Výstup (stdout) piste ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | 5 5 2 4 15 8 10 7 8 14 18 20 9 6 13 21 24 10 11 12 15 17 28 7 8 10 12 | 9 2 7 8 14 18 21 24 17 12 Ale i další řešení.| 13 2 7 9 10 11 12 13 14 18 21 24 17 12 | žádný | 0 | ==== Příklad 14 – kopec_2_04 ==== V tomto a dalších příkladech může být řešení i více, rozhodující je délka cesty a její sklon (stoupání, resp. klesání). Pokud vám vychází jiná řešení, zkontrolujte si tyto parametry cesty. ^ Vstup (stdin) ^ Výstup (stdout) lift ^ Výstup (stdout) piste ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | 5 5 2 4 6 8 10 12 14 16 14 12 23 24 25 11 19 21 22 24 17 15 1 3 5 7 9 | 9 2 12 23 24 25 24 17 15 9 | 13 2 4 6 8 10 12 14 16 25 24 17 15 9 | žádný | 0 | ==== Příklad 15 – kopec_2_05 ==== ^ Vstup (stdin) ^ Chybový výstup (strerr) ^ Návratová hodnota ^ | 8 8 1 15 14 13 12 11 10 9 2 16 24 23 22 21 20 8 3 17 25 32 30 29 19 7 4 18 26 33 32 28 18 6 5 19 27 34 31 27 17 5 6 20 28 29 30 26 16 4 7 21 22 23 24 25 15 3 8 9 10 11 12 13 14 2 | žádný | 0 | ^ Výstup (stdout) lift | 15 1 2 3 4 5 19 27 34 31 27 17 5 4 3 2 | ^ Výstup (stdout) piste | 65 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 33 32 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 | Pro lanovku i sjezdovku existuje více možných výstupů. ==== Další testy ==== **Příklad 14 - kopec_2_06** Vstup: Kopec velikosti 10x10. **Příklad 15 - kopec_2_07** Vstup: Kopec velikosti 15x20. **Příklad 16 - kopec_2_08** Vstup: Kopec velikosti 20x30. Dále je řešení testováno na datech větších velikostí - kopce velikosti až $ 200 \times 300$ bodů. ====== Dodatek k postupu řešení ====== Při řešení úlohy - viz [[courses:b6b36dsa:ukoly:hw04#priklad_1_kopec_1_01|příklad 1 (lift)]] lze **pro cestu nahoru** získat například (viz popis [[courses:b6b36dsa:ukoly:hw04#algoritmus_reseni_ulohy|algoritmu]]): {[0, 0, [0, 0]], [1, 1, [0, 0]], [2, 1, [0, 1]], [0, 0, [0, 0]], [1, 1, [1, 0]], [3, 1, [0, 2]], [0, 0, [0, 0]], [1, 1, [2, 0]], [4, 1, [1, 2]]} Odpovídající matice pro cestu dolů obsahuje v tomto případě samé nuly. Z matice je zřejmé, že délka maximální cesty je 4. Z odpovídajícího prvku matice na indexu [2, 2] lze dále zjistit, že maximální sklon cesty je 1 a předchozím bodem cesty je bod [1, 2]. Cesta pro lanovku do bodu [1, 2] má délku 3 (logicky o jedničku menší), sklon je stejný a předchozím bodem je bod [0, 2]. Takto pokračujeme při rekonstrukci cesty až do bodu [0, 0]. Matici konstruujeme postupně z bodu [0, 0] pro cestu nahoru a z bodu [n - 1, m - 1] pro cestu dolů. Stanovíme podmínky pro konstrukci "následujících" bodů matice. Hlavní podmínkou je neustále stoupající nadmořská výška a pak sklon svahu podle zadání úlohy. Při konstrukci cesty pro lanovku je z bodu na souřadnicích ''[x, y]'' nutné prohledat body vpravo (souřadnice ''[x + 1, y]'') a dole (souřadnice ''[x, y + 1]''). Při konstrukci cesty pro sjezdovku je nutné prohledat pro každý bod všechny směry. Hodnoty pro jednotlivé body (délka a sklon cesty) se mohou průběžně zlepšovat, a proto je potřeba body průběžně ukládat do fronty, která určí postup zpracování jednotlivých bodů. Při řešení úlohy - viz [[courses:b6b36dsa:ukoly:hw04#priklad_11_kopec_2_01|příklad 11 (lift)]] lze **pro cestu nahoru** získat například následující matici: {[0, 0, [0, 0]], [1, 1, [0, 0]], [2, 1, [0, 1]], [0, 0, [0, 0]], [1, 1, [0, 0]], [2, 4, [1, 0]], [0, 0, [0, 0]], [0, 0, [0, 0]], [2, 1, [1, 0]], [3, 1, [2, 0]], [0, 0, [0, 0]], [0, 0, [0, 0]]} Odpovídající matice **pro cestu dolů** vypadá pak následovně: {[0, 0, [0, 0]], [0, 0, [0, 0]], [0, 0, [0, 0]], [2, 1, [1, 3]], [0, 0, [0, 0]], [3, 3, [1, 2]], [2, 1, [1, 3]], [1, 1, [2, 3]], [0, 0, [0, 0]], [2, 2, [2, 2]], [1, 1, [2, 3]], [0, 0, [0, 0]]} Vidíme, že vrcholem cesty je bod [1, 1] a celková délka cesty je 5 (cesta prochází přes 6 bodů). Stejnou délku cesty lze získat i v bodě [2, 1], tam je ale menší sklon cesty - ve směru nahoru i ve směru dolů. Při řešení úlohy - viz [[courses:b6b36dsa:ukoly:hw04#priklad_11_kopec_2_01|příklad 11 (piste)]] lze **pro cestu nahoru** získat například následující matici: {[0, 0, [0, 0]], [1, 1, [0, 0]], [2, 1, [0, 1]], [0, 0, [0, 0]], [1, 1, [0, 0]], [4, 2, [2, 1]], [0, 0, [0, 0]], [0, 0, [0, 0]], [2, 1, [1, 0]], [3, 1, [2, 0]], [0, 0, [0, 0]], [0, 0, [0, 0]]} Odpovídající matice **pro cestu dolů** vypadá pak následovně: {[0, 0, [0, 0]], [0, 0, [0, 0]], [0, 0, [0, 0]], [2, 1, [1, 3]], [0, 0, [0, 0]], [3, 2, [2, 1]], [2, 1, [1, 3]], [1, 1, [2, 3]], [0, 0, [0, 0]], [2, 2, [2, 2]], [1, 1, [2, 3]], [0, 0, [0, 0]]} Vrcholem cesty je opět bod [1, 1]. ====== Odevzdání a hodnocení ====== Úlohu je možné řešit v programovacím jazyce ''Java'', ''Python'' nebo ''C/C++''. Veřejné testovací soubory - {{:courses:b6b36dsa:ukoly:DSA_HW04.zip?400|DSA_HW04}}. ^ Název úlohy v BRUTE | **HW04** || ^ Odevzdávané soubory | ''hill.py'' – zdrojový soubor v python3 || | ::: | ''Hill.java'' – zdrojový soubor v Java, název třídy Hill || | ::: | ''hill.c'', resp. ''hill.cpp'' – zdrojový soubor v C/Cpp || ^ Argumenty programu | ''lift'' – pro vyhledání cesty pro lanovku || | ::: | ''piste'' – pro vyhledání cesty pro sjezdovku || | ::: | žádný – vyhledání cesty pro lanovku a následně pro sjezdovku || ^ Kompilace pro jazyk C | clang -Wall -Werror -pedantic -std=c99 clang -Wall -Werror -pedantic -std=c+ +17 || ^ Kompilace a spuštění \\ pro jazyk Java | javac *.java java -classpath Hill || ^ Očekávaná složitost | Výpočet pomocných tabulek v čase cca $\mathcal{O}(n^2)$ || | ::: | Nalezení cesty v čase cca $\mathcal{O}(n)$ || | ::: | Koeficient pro čas výpočtu $3.0$ || ^ Procvičované oblasti | dynamické programování memoizace || ^ Bodové hodnocení (celkem 15 bodů) | 3 body | parametr ''lift'' - kopec_1_01 – kopec_1_10 + 5 skrytých testů | | ::: | 2 body | parametr ''lift'' - kopec_2_01 – kopec_2_08 + 8 skrytých testů | | ::: | 3 body | parametr ''lift'' - 15 skrytých testů na velkých maticích \\ řešení časově stejné nebo lepší než referenční řešení | | ::: | 2 body | parametr ''piste'' - kopec_1_01 – kopec_1_10 + 5 skrytých testů | | ::: | 2 body | parametr ''piste'' - kopec_2_01 – kopec_2_08 + 8 skrytých testů | | ::: | 3 body | parametr ''piste'' - 15 skrytých testů na velkých maticích \\ řešení časově stejné nebo lepší než referenční řešení | ^ Maximální počet uploadů | ''20'' Více uploadů je možných s odpovídající bodovou ztrátou ||