[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Magic Squares  XML
Forum Index » Други задачи
Author Message
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)... Но бидејќи со секоја трансформација се менуваат група на полиња со група на полиња, не знам како би го направил тоа... Ако знае некој да ми помогне, или пак ако има некоја друга идеа би било супер
[MSN]
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 а?

Ајде вака. За да не ти ја расипам задачата, ќе ти дадам три хинтови ама ќе го обојам текстот во бело така да ќе можеш да ги читаш еден по еден со маркирање на текстот и притоа да размислиш убаво. Мислам дека уште после првиот (или максимум вториот) би требало да можеш да ја решиш задачата, така да потруди се.

Прво, колку различни можни распореди на табелата постојат?

Второ, дали може наместо полињата да бидат темиња, самата табела, т.е. нејзиниот распоред да е теме?

Трето, дали има потреба од Флојд-Варшал, или може и некој поедноставен алгоритам?
hristijan



Joined: 24/01/2010 09:42:46
Messages: 49
Offline

Не мораш да размислуваш колку можни распределби на таблата постојат, мали се ограничувањата и така поминува и не мора да ја транформираш табелата во теме, и без тоа поминува на меморија ако користиш bitset
jovank



Joined: 01/01/2010 16:17:42
Messages: 127
Offline

ејј фала многу, вториов хинт е тој што стварно ми разјасни некои ствари (после првиот, за момент помислив на brute force )
[MSN]
obi1kenobi



Joined: 18/02/2010 20:01:33
Messages: 168
Offline

Ете што му треба на форумов:

Mark thread RESOLVED опција.
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

[MSN]
jovank



Joined: 01/01/2010 16:17:42
Messages: 127
Offline

мал bug има форумов со знаците < и >
[MSN]
dejandenib



Joined: 12/02/2010 12:40:13
Messages: 33
Offline

Ех Јоване додека решиш некоја задача многу хинтови ти требаат.Obi1kenobi што ти кажа да користиш побрз алгоритам од Флојд Варшал, не мислеше на дикстра, постои и побрз алгоритам за да се реши задачава.
ps: queue е побрзо од priority queue, ако го користиш како што треба.
jovank



Joined: 01/01/2010 16:17:42
Messages: 127
Offline

пробав прво со бфс, али и тоа ми падна на време... :/
[MSN]
dejandenib



Joined: 12/02/2010 12:40:13
Messages: 33
Offline

БФС е задачава, мора да пројде на време, имаш 8! состојби, пo ~8^2 пресметки за секоја.Тоа се ~2580480 процеси. За 1 секунда ќе работи. Ептен комплицираш со дикстра.
 
Forum Index » Други задачи
Go to:   
Powered by JForum 2.1.8 © JForum Team