|
Titlul: 053 Car Scris de: Mircea Pasoi din Februarie 24, 2005, 20:56:01 Aici puteţi discuta despre problema Car (http://infoarena.ro/problema/car).
Titlul: 053 Car Scris de: Patriche Daniel din Martie 07, 2005, 10:58:12 indexarea pozitiilor initiale si finale incepe de la 0 sau la 1 ? adika primul element din matrice e A[0,0] sau A[1,1] ?
Titlul: tst 9 Scris de: Marin Radu din Martie 09, 2005, 10:21:35 Nasol testu 9. :-k L-a facut cineva din prima? Tot iau TLE.
Da cu bellman-ford a facut careva?, eu asa am facut si merge binisor, poate chiar mai bine decat Dijkstra cu costuri mici. M-am uitat la solutia prezentata oficial, pare simplu, dar tocmai constanta din fata lu' N*M care este 3*8*(cate operatii efectuate cu un nod din lista) si care nu este precizata face diferenta de scor. In cazurile astea constanta n-ar trebui ignorata, e importanta!!! Titlul: 053 Car Scris de: Cosmin Negruseri din Martie 09, 2005, 15:39:30 Testul 9 este cel mai costisitpr ca timp si pentru solutia noastra care sta pe el in jur de 0.5 secunde.
Titlul: 053 Car Scris de: cip2005 din Martie 23, 2005, 02:04:50 Eu totusi nu inteleg o chestie in rezolvare, legata de listele folosite.. :
Citat Daca aceste costuri sunt mici atunci si costul final al drumului de la sursa la destinatie va fi mic deci ne permitem sa folosim pentru fiecare valoare posibila a costului unui drum de la sursa la destinatie cate o lista. si totusi ce aflam noi mai tarziu?! ca sunt 3 liste defapt! : Citat Am folosit numai trei liste pentru ca am tinut cont de optimizarea precizata mai sus de a nu folosi numai curbele la 0 grade, 45 grade si 90 grade. va rog sa ma ajutati si pe mine sa ma lamuresc... ](*,) [/quote] Titlul: 053 Car Scris de: Cosmin Negruseri din Martie 23, 2005, 12:12:53 Pai ai daca la pasul actual expandezi noduri la care s-a ajuns cu costul C, atunci vei modifica numai listele cu costul C, C+1 si C+2, deci listele nu cu cost C-1 C-2 .... 0 nu mai are rost sa le folosesti, iar listele de cost C+3, C+4 .... sunt inca nepopulate, deci poti folosi numai 3 liste si faci ceva de genu:
Cod:
Tot asa faci la unele programari dinamice in care in loc sa folosesti o matrice intreaga folosesti doar doua linii, linia curenta si linia urmatoare. Titlul: 053 Car Scris de: Paul-Dan Baltescu din Martie 05, 2006, 00:33:52 Puteti sa-mi spuneti cat va da pe testul:
15 15 8 8 10 14 1 0 0 0 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 1 1 0 0 0 1 0 0 0 1 1 0 1 1 0 1 0 0 1 0 0 0 0 1 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 1 0 0 1 0 1 1 0 0 0 1 0 1 0 1 1 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 1 1 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 1 0 0 0 1 1 1 0 1 0 0 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 0 0 1 1 1 1 1 0 0 1 0 0 0 0 0 Titlul: 053 Car Scris de: Bogdan-Cristian Tataroiu din Martie 05, 2006, 09:14:30 2 :-k
Titlul: Raspuns: 053 Car Scris de: Marius Stroe din Aprilie 07, 2006, 21:15:10 Ma chinui de o zi sa trec testele 7 si 10, e ceva special la ele ? Pot sa le rezolv luand numai curbe de 0 , 45 si 90 de grade, nu ? :-s
Titlul: Raspuns: 053 Car Scris de: Cosmin Negruseri din Aprilie 07, 2006, 21:21:34 Poti sa o rezolvi doar cu curbe de 0 si 45, fara 90, daca vei considera ca miscarea pe loc cu 45 de grade costa 1.
Titlul: Raspuns: 053 Car Scris de: Marius Stroe din Aprilie 08, 2006, 10:12:23 Nu sunt sigur daca am rezolvat corect, pentru ca nu trect testele 7 si 10, dar 9 dureaza 0.22 s.
Am incercat sa rezolv problema cam asa: iau numai curbe de 0, 45, 90 de grade. Cand verific vecinii nodului curent si gasesc un cost mai mic sau egal il pun in coada. Coada asta are trei "niveluri", adica daca nodul curent se afla pe nivelul k , atunci cand inserez un nod vecin il pe nivelul (k + dir) % 3, unde dir e 0 daca se continua pe directia respectiva, e 1 daca e o curba de 45 si 2 daca e curba de 90 de grade. Continui pana cand "golesc" nivelul curent, apoi trec la urmatorul. Totul se termina cand toate nivelurile sunt goale. Putin ajutor! :D Titlul: Raspuns: 053 Car Scris de: Filip Cristian Buruiana din Aprilie 08, 2006, 11:58:11 Ai verificat sa nu adaugi de doua ori un nod in liste? Adica cand ai adaugat un nod intr-o lista pentru prima data, il marchezi ca FOLOSIT si nu il mai adaugi in vreuna din liste si a doua oara.
Titlul: Raspuns: 053 Car Scris de: Marius Stroe din Aprilie 08, 2006, 12:14:12 Nu gasesc un exemplu, dar daca nu pun un nod de mai multe ori (de cel mult trei ori, deoarece poti intra in el din cel mult trei directii) pot sa continui de aici cu un cost mai mare, depinzand de directie. Cum zici tu iau 50 p. :-k
Titlul: Raspuns: 053 Car Scris de: Cosmin Negruseri din Aprilie 08, 2006, 12:47:14 Pentru fiecare nod tii minte distanta minima cu care ai ajuns la el, si cand vrei sa il adaugi la o lista, il adaugi doar daca indicele real al listei este mai mic decat distanta calculata pana in momentul curent.
Titlul: Răspuns: 053 Car Scris de: Chis Raoul din Iunie 19, 2007, 14:28:17 Pentru exemplul din enunt, raspunsul nu ar trebui sa fie 11 ? Ionel ia 3 curbe de 90 de grade si una de 135 ... :|
Titlul: Răspuns: 053 Car Scris de: Lodoaba Sorin din Martie 17, 2011, 14:09:44 @chris nup, ia doar curbe de 45; iar ultima de pe ultima coloana este de 135
Titlul: Răspuns: 053 Car Scris de: George Marcus din Martie 17, 2011, 18:29:16 Nu sunt curbe de 135 in exemplu. Ai 4 de 90 si una de 45.
|