# zkouska 26.6

<{ForumPost(poster="Jakobicek", timestamp=2006-06-26 15:37:11)}>
mel jsem stesti pri malem prikladu -- dostal jsem BVS delete :wink:   
zadani velkeho prikladu:  
behem prazdnin mate v planu navstivit takove koncerty abyste si poslechly co nejvice muziky... kazdy den stihnete maximalne 1 koncert  
koncerty se nachazi v ruznych mestech mezi mesty se vzdy da prejet behem jednoho dne  
na koncertu se vzdy hraje nekolik skladeb daneho zpevaka  
ohodnoceni koncertu je suma delky vsech pisnicek  
za prazdniny muzete najet maximalne 2000 km...  :evil:   
mezi kazdymi dvema mesty existuje **cesta celociselne delky **ne vsak nutne prima trat  
pocet pisnicek max 10000  
pocet dnu 92  
pocet zpevaku max 100  
pocet mest max 100  
na jednom koncertu max 100 pisnicek  
pamet 5MB (relativne volne omezeni, kdyz nestaci je mozno v nouzi pouzit vice)  
nastin reseni...: ano uloha MA polynomialni algoritmus...  
timto beru vsem vcetne me  :wink: kteri se snazili najit nejakou heuristiku iluze  
holanovo reseni vyuziva trirozmernou tabulku indexovanou dny mesty a kilometry... :idea:   
ustni zkouska:  
holan si nebyl jist korektnosti meho reseni maleho prikladu ale nakonec se nechal presvedcit ze program funguje  :)   
u velkeho byl zklaman ze jsem neprisel na lepsi algoritmus nicmene moji heuristiku uznal jako celkem rozumny napad.. je vazne v pohode.. kazdou myslenku s vami rozebere a vetsinou pripocita fiktivni kladne body  
pak se me zeptal na dynamicke programovani :lol:   
a nasledne prohlasil ze je to mezi 1 a 2 a zeptal se na vytvoreni haldy v case o(n)... na to jsem si vzpominal jen ztuha ale nakonec jsem to dal dohromady  
nejdulezitejsi je jak uz tu bylo nekolikrat napsano neprustrelne reseni maleho prikladu... obtiznost malych prikladu je velmi rozmanita.. je to o stesti...  
k velkemu je pak dulezite alespon neco rozumneho napsat... nemusi to byt zrovna to optimalni i s tim se da na zkousce uspet  
na ustni se hlavne nestresovat...
<{/ForumPost}>

<{ForumPost(poster="lingvik", timestamp=2006-06-27 20:05:47)}>
Jen drobet mých loňských zkušeností: malý příklad je sice fajn, ale nebojte, jde to i bez něho. Já ho měl úplně špatně, ale protože se dr. Holanovi můj velký příklad nebývale líbil, tak jsem přesto odcházel s jedničkou.
<{/ForumPost}>

<{ForumPost(poster="Jakobicek", timestamp=2006-06-28 07:19:33)}>
jiste jde to i naopak   8)   jenom si myslim ze je z psycholgickeho hlediska velmi prijemne mit za sebou pred velkym solidne vyreseny maly priklad.. zvlast pokud velky nebyl snadny... co jsem mluvil se spolubojovniky tak nikoho polynomialni reseni nenapadlo...
<{/ForumPost}>