Author |
Message |
24/05/2011 15:34:09
|
jovank
Joined: 01/01/2010 16:17:42
Messages: 127
Offline
|
Малку помош ако може
http://olympiads.win.tue.nl/ioi/ioi96/contest/ioi96m.html
На линков има една задача, Magic Squares... Идеата ми е да направам граф од табелата (темиња се сите полиња, врска помеѓу две полиња постои ако може со некоја од трансформациите A, B и C да се сменат тие две полиња), и после некако да ги најдам најкратките патишта помеѓу полињата кои треба да дојдат до своето место (најверојатно со алгоритамот на Floyd-Warshall)... Но бидејќи со секоја трансформација се менуваат група на полиња со група на полиња, не знам како би го направил тоа... Ако знае некој да ми помогне, или пак ако има некоја друга идеа би било супер
|
|
|
24/05/2011 16:32:47
|
obi1kenobi
Joined: 18/02/2010 20:01:33
Messages: 168
Offline
|
jovank wrote:Малку помош ако може
http://olympiads.win.tue.nl/ioi/ioi96/contest/ioi96m.html
На линков има една задача, Magic Squares... Идеата ми е да направам граф од табелата (темиња се сите полиња, врска помеѓу две полиња постои ако може со некоја од трансформациите A, B и C да се сменат тие две полиња), и после некако да ги најдам најкратките патишта помеѓу полињата кои треба да дојдат до своето место (најверојатно со алгоритамот на Floyd-Warshall)... Но бидејќи со секоја трансформација се менуваат група на полиња со група на полиња, не знам како би го направил тоа... Ако знае некој да ми помогне, или пак ако има некоја друга идеа би било супер
Решаваш USACO а?
Ајде вака. За да не ти ја расипам задачата, ќе ти дадам три хинтови ама ќе го обојам текстот во бело така да ќе можеш да ги читаш еден по еден со маркирање на текстот и притоа да размислиш убаво. Мислам дека уште после првиот (или максимум вториот) би требало да можеш да ја решиш задачата, така да потруди се.
Прво, колку различни можни распореди на табелата постојат?
Второ, дали може наместо полињата да бидат темиња, самата табела, т.е. нејзиниот распоред да е теме?
Трето, дали има потреба од Флојд-Варшал, или може и некој поедноставен алгоритам?
|
|
|
24/05/2011 16:44:03
|
hristijan
Joined: 24/01/2010 09:42:46
Messages: 49
Offline
|
Не мораш да размислуваш колку можни распределби на таблата постојат, мали се ограничувањата и така поминува и не мора да ја транформираш табелата во теме, и без тоа поминува на меморија ако користиш bitset
|
|
|
24/05/2011 19:49:05
|
jovank
Joined: 01/01/2010 16:17:42
Messages: 127
Offline
|
ејј фала многу, вториов хинт е тој што стварно ми разјасни некои ствари (после првиот, за момент помислив на brute force )
|
|
|
24/05/2011 22:31:45
|
obi1kenobi
Joined: 18/02/2010 20:01:33
Messages: 168
Offline
|
Ете што му треба на форумов:
Mark thread RESOLVED опција.
|
|
|
31/05/2011 00:29:19
|
jovank
Joined: 01/01/2010 16:17:42
Messages: 127
Offline
|
Сега ми паѓа на време... има некој идеа како да го убрзам решениево?
>
This message was edited 3 times. Last update was at 31/05/2011 00:32:00
|
|
|
31/05/2011 00:33:06
|
jovank
Joined: 01/01/2010 16:17:42
Messages: 127
Offline
|
мал bug има форумов со знаците < и >
|
|
|
31/05/2011 00:51:50
|
dejandenib
Joined: 12/02/2010 12:40:13
Messages: 33
Offline
|
Ех Јоване додека решиш некоја задача многу хинтови ти требаат.Obi1kenobi што ти кажа да користиш побрз алгоритам од Флојд Варшал, не мислеше на дикстра, постои и побрз алгоритам за да се реши задачава.
ps: queue е побрзо од priority queue, ако го користиш како што треба.
|
|
|
31/05/2011 15:35:50
|
jovank
Joined: 01/01/2010 16:17:42
Messages: 127
Offline
|
пробав прво со бфс, али и тоа ми падна на време... :/
|
|
|
31/05/2011 17:13:20
|
dejandenib
Joined: 12/02/2010 12:40:13
Messages: 33
Offline
|
БФС е задачава, мора да пројде на време, имаш 8! состојби, пo ~8^2 пресметки за секоја.Тоа се ~2580480 процеси. За 1 секунда ќе работи. Ептен комплицираш со дикстра.
|
|
|
|