======== 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 ||