|
Titlul: 263 Patrol Scris de: ditzone din August 03, 2006, 21:56:02 Aici puteţi discuta despre problema Patrol (http://infoarena.ro/problema/patrol).
Titlul: Raspuns: 263 Patrol Scris de: Paul-Dan Baltescu din August 04, 2006, 12:37:56 Am citit solutia oficiala si am o nedumerire.
Presupunand ca am un graf format dintr-un lant cu n>120 si 0 politisti, nu inseamna ca hotul ajunge la destinatie intr-un timp > 120? Titlul: Raspuns: 263 Patrol Scris de: Filip Cristian Buruiana din August 17, 2006, 10:09:40 Ba da, dar tu in graful nou construit o sa ai urmatoarele noduri:
(1 1), (2 1), (3 1)... (120 1), (121 1). Perioada este 1, nu timpul efectiv care este 121! Titlul: Raspuns: 263 Patrol Scris de: adrian din August 25, 2006, 15:54:51 any ideas how to build a generator and a brute force for this problem?
Titlul: Raspuns: 263 Patrol Scris de: Filip Cristian Buruiana din August 25, 2006, 16:34:10 Poti incerca teste random. Generezi muchii pentru graful dat pana cand ai ajuns la numarul de M muchii. De fiecare data cand ai o muchie noua generata verifici sa nu mai fi fost creata anterior ( faci asta folosind un tabel de hash ). Pentru a crea un traseu alegi un nod din graf si apoi tot alegi un nod vecin ultimului nod si care nu apartine drumului.
Pentru teste mici brute force poate insemna chiar back. Daca nu, poti implementa djikstra in timp patratic in numarul de noduri. Titlul: Raspuns: 263 Patrol Scris de: adrian din August 25, 2006, 16:45:38 eu ma refeream ,sa construiesc teste intotdeauna cu o solutie dar banuiesc ca voi generati teste si verificati daca exista solutie si abia apoi il bagati la arhiva ca test oficial
Titlul: Raspuns: 263 Patrol Scris de: Filip Cristian Buruiana din August 25, 2006, 18:33:29 Da, pe teste mari asa se face :)
|