|
Titlul: 977 Semafoare Scris de: Paul-Dan Baltescu din Februarie 21, 2010, 13:49:26 Aici puteti discuta despre problema Semafoare (http://infoarena.ro/problema/semafoare).
Titlul: Răspuns: 977 Semafoare Scris de: Andrei Misarca din Februarie 28, 2010, 00:38:19 Am o întrebare în legătură cu al doilea exemplu. Cum dă 19? Mie îmi dă 15 pe următorul traseu(am pus nodurile și timpu cât durează de când începe până traversează intersecția cu pricina):
0 5 -> 2 1 5 -> 4 1 4 -> 6 1 3 -> 9 2 3 -> 10 2 2 -> 12 3 2 -> 14 Deci în 3 1 va ajunge în momentul 15. :? Titlul: Răspuns: 977 Semafoare Scris de: Paul-Dan Baltescu din Februarie 28, 2010, 08:51:07 Citat Odată intrată în intersecţie o maşină îşi poate continua drumul mai departe sau poate vira spre stânga sau spre dreapta. Tu in intersectia (0, 5) te intorci, ceea ce nu e permis. Titlul: Răspuns: 977 Semafoare Scris de: Andrei Misarca din Februarie 28, 2010, 10:05:04 N-am citit restricția respectivă considerând că oricum nu are de ce să se întoarcă (iar în afară de cazul în care se întoarce în prima intersecție, nu are de ce să se întoarcă).
Ca o optimizare a soluției oficiale, nu are sens să reținem maximul pentru un triplet (i, j, k), ci doar pentru perechea (i, j), întrucât direcția din care se vine nu are relevanță decât pentru a calcula cât timp stă la semafor. De aceea, când trece dintr-o stare în alta, se poate calcula timpul noii stări ca fiind timpul vechii stări + timpul cât stă la semafor în noua stare + 1. Deși complexitatea teoretică este tot O(N*M), în realitate merge mult mai repede (sub 0,2 secunde). P.S. Linku către problemă din primul post este greșit (scrie infoarnea în loc de infoarena). :) Titlul: Răspuns: 977 Semafoare Scris de: Vidrean Mihai din Septembrie 12, 2012, 16:10:56 Buna!Imi puteti explica un pic mai detaliat rezolvarea problemei.Am citit solutia oficiala,dar nu am inteles prea bine cum se face acea parcurgere folosind cele 5 cozi si matricea D cu cele 3 dimensiuni :sad:.
Multumesc. Titlul: Răspuns: 977 Semafoare Scris de: Paul-Dan Baltescu din Septembrie 12, 2012, 22:16:38 Ai putea incerca sa rezolvi problema http://infoarena.ro/problema/padure mai intai. Aceasta problema este asemanatoare, dar mai simpla si sunt ceva explicatii si pe forum despre cum se rezolva in caz ca nu te descurci.
|