19 Mar
2011
19 Mar
'11
12:18 a.m.
Sziasztok!
Én pedig a maximális minimum távolságos "Safest Place" feladattal
foglalkoztam egy kicsit. Csináltam hozzá C#-ban egy kis szemléltető
programocskát [1], ami persze tesztelni is jó, hogy miként alakul a rács.
Hogy jól vizualizálható legyen, ez csak 2D-ben működik, így oct-tree
helyett quad-tree-t használ, de a működése alapelvét tekintve ugyanaz,
mint a 3D verziónak.
Közben amúgy rájöttem, hogy egy jó megoldás kapható úgy is, ha építünk a
pontokra egy Voronoi-diagramot ([2]), ennek ugyanis valamelyik csúcspontja
lesz a megoldás. Persze nem valószínű, hogy valakinek ezt lenne ideje
lekódolni...
[1]: http://cs.bme.hu/acm/felkeszito2011/05/SafestPlaceVisu.zip
[2]: http://en.wikipedia.org/wiki/Voronoi_diagram
Üdv,
Balázs
On Fri, 18 Mar 2011 23:01:07 +0100, NGG <ngg(a)ngg.hu> wrote:
megcsinaltam alien gamet, de nem tudtam bekuldeni,
mert szar a
bekuldorendszeruk es amig szamol visszafele hogy 6 perc van hatra,
kozbe irja hogy time expired azzal parhuzamosan...
nagyon szep megoldasa van kulonben
6 perc van megoldani, bekuldessel egyutt, szoval olyan megoldas kell,
ami kb 5 perc alatt lefut
enyem O(n^2*log(n)), es kb 5 mp alatt lefut a nagy inputfajlra, amiben
kb 45 bazinagy eset van
nem szeretnem elarulni megoldast (majd jovohet penteken), csak
sejtesekrol par szo:
- tenyleg nem szamit hogy ki mit lep, mindenkepp ugyanaz nyer (sot a
lepesszam is azonos mindig)
- a masik sejtes nem igaz, hogy 1-et irhatunk akarmilyen pozitiv szam
helyett (pl "0 -1 1 0"-ra 1 lepes utan van vege, amig "0 -1 2 0"-ra
2
lepes utan van vege)
ngg
_______________________________________________
acm-valogato mailing list
acm-valogato(a)sziami.cs.bme.hu
http://sziami.cs.bme.hu/mailman/listinfo/acm-valogato