# 2010

<{ForumPost(poster="Anonymous", timestamp=2010-05-31 12:36:55)}>
Zadával Holan, úloha koncert  
[26.6.2006](/NPRG031/zkouska%2026.6%20holan)  
[http://www.martinvseticka.eu/index.php? ... se&page=40](http://www.martinvseticka.eu/index.php?sekce=browse&page=40)  
nikde není vyloženě napsané řešení .. má někdo nějaké vyloženě dobré?  
ještě pamět byla omezená na 20 MB místo 5MB .. odpovídá přesně na tabulky z návodu k řešení, byla trochu pozměněna čísla
<{/ForumPost}>

<{ForumPost(poster="Tomgr", timestamp=2010-05-31 19:48:52)}>
Já sem měl celkem dobrej pocit a měl jsem to se složitostí O(počet kilometrů x počet dní x počet měst x počet měst) řešený přes dynamický programování - hlavní nástroje trojrozměrný pole \[den,mesto,kilometr] s longem celkovy_cas a bytem odkud, matice nejkratších vzdáleností mezi městama a pole \[mesto,den] obsahující délku nejlepšího koncertu a jeho název. Ale správností si budu jistej, až mi to potvrdí na ústním, doufejme že Holan xD (btw. novej účes i tričko, všimli jste si? :mrgreen: )
<{/ForumPost}>

<{ForumPost(poster="Dr.Eddy", timestamp=2010-06-01 10:46:46)}>
postup pres 3-rozmernou tabulku v dynamickem programovani je spravny. Naopak naprosto chybny je postup pres hledani do hloubky (backtracking), za coz mi dal trojku a mohl jsem byt rad. Topfer je ale hodny clovek, na teorii se snazi najit neco, cemu rozumite. Jen je potreba mluvit jasne a formulovat presne.
<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2010-06-01 14:29:23)}>
zatraceně až teď mi došlo, že sem všechno cpal do 20kB místo MB .. aspon že vim, že je to za 3 .. btw co je tak špatnýho na exponenciálnim prohledávání do hloubky ;-)
<{/ForumPost}>

<{ForumPost(poster="Tomgr", timestamp=2010-06-01 17:12:19)}>
No jestli to bylo exponenciální tak, že si zkoušel pro každej den všechny města, ve kterejch se hraje, tak by ses k výsledku nedostal ani kdyby se počítače každej rok 2x zrychlovali a pár let před smrtí to pustil na tom nejlepším, ne? :-D
<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2010-06-01 20:05:10)}>
Ba co líp, bylo to exponenciální podle počtu koncertů  :D .. nevim proč ale tabulka města*dni se mi už nevešla do paměti  :D  .. moje řešení by si nepustilo ani moje pravnouče :D
<{/ForumPost}>

<{ForumPost(poster="J4rd4", timestamp=2010-06-09 15:18:56)}>
Zdar,  
nenašla by se nějaká dobrá duše, která by ten algoritmus vyžívající trojrozměrnou tabulku blíž popsala??? Asi si to jen nedokážu představit jak by to vypadalo...  
Dík...  :wink:
<{/ForumPost}>

<{ForumPost(poster="Tomgr", timestamp=2010-06-09 21:19:38)}>
Tak napřed si připravit data z těch souborů do ptřebnejch polí. To jsem dělal ukládáním koncertů do spojáku, na každej koncert navěsit název písničky, město dát do matice vzdáleností a přiřadit mu číslo od 1 do 20, písničku s časem zahešovat. Pak projít ten spoják koncertů a u každýho koncertu spočítat délku (po jednom průchodu už mám všechny písničky nahešovaný, tak znám jejich dýlky) a pak pro každý město a den vybrat nejdelší koncert.  
Vedle toho na města spustit třeba floyd-warschalla.  
Uvolnit pamět.  
Udělat si výše zmíněnou trojrozměrnou tabulku.  
A začínám vyplňovat:  
Jednu for cyklama přes všechny dny, přes všechny města, přes všechny kilometry.  
V prvním kroku začínám ve dni 1, v praze, a na nula kilometrech. Udělám for cyklus přes všechny města (včetně toho, kde teď jsem) a uložím to pole indexovanýho \[den+1, město_do_kteryho_jdu, kilometry navýšený o vzdálenost kterou jsem urazil/může zůstat i stejný] hodnotu navýšenou o to, co v danej den a pro daný město dokážu slyšet. Pokud tam už něco je, tak vyberu samozřejmě to, co má větší hodnotu.  
  
Na konci prohledám ve dni 92 všechny města a všechny možný kilometry.  
Vyhledávání cesty zpátky:  
Položka toho trojrozměrnýho pole bude záznam, kterej bude mít nejen celkovej čas, ale i město, odkud sem přišel. Pak to jednoduše proskáču až do dne 1.
<{/ForumPost}>