2010

Zadával Holan, úloha koncert
http://forum.matfyz.info/viewtopic.php? ... cert#p8270
http://www.martinvseticka.eu/index.php? ... se&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

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: )

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.

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 ;-)

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

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

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:

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.