Решение на задачата ТВ Одмор (рекурзија за дел од поените, динамичко програмирање за сите поени)
Решение на задачата Затвор (бинарно пребарување со BFS)
- имаше многу натпреварувачи кои беа блиску до решавање на оваа задача, па ќе оставам уште неколку дена некој да го прикачи своето решение (откога ќе ја реши и ќе му поминат сите тест случаи во тренинг делот). Ако никој не ја прикачи до тогаш - ќе го ставам нашето решение.
This message was edited 4 times. Last update was at 17/03/2011 21:00:07
Eve go moeto resenie.
Prvo pustam obicno BFS od sekoe G vo isto vreme i taka za sekoe pole go dobivam rastojanieto do najbliskiot strazar.
Potoa resenieto koristi priority_queue za da implementira nekoj vid na minimum spanning tree so Primov algoritam )). Razlikata e toa sto tuka celo vreme go zemame poleto so najgolema vrednost namesto so najmala pa ova bi bilo "maximum spanning tree"... Mislam deka ima ista slozenost kako toa so binary search, ako ne i podobra.
Otprilika O( n * m * log(n*m) ) mislam. Ako sum greska popravete me