|
Titlul: 1128 Poligoane Scris de: Andrei Parvu din Aprilie 10, 2011, 10:51:19 Aici puteti discuta despre problema Poligoane (http://www.infoarena.ro/problema/poligoane).
Titlul: Răspuns: 1128 Poligoane Scris de: Sorin Rita din Aprilie 10, 2011, 12:42:29 Imi da si mie cineva o idee de rezolvare ? ](*,)
Titlul: Răspuns: 1128 Poligoane Scris de: Simoiu Robert din Aprilie 10, 2011, 16:47:13 Faci recurenta dp[ i ][j] - numarul de moduri sa imparti i bete in poligoane, unde cel mai mare poligon are j bete. Rezultatul o sa fie suma ( dp[N][ i ] ), i = 3, N. Daca ai nevoie de alt ajutor sa-mi spui.
Titlul: Răspuns: 1128 Poligoane Scris de: Petru Trimbitas din Mai 27, 2011, 17:41:28 Cred ca ar trebui pus poligoane convexe regulate pt ca pt n=6 poti forma si un dreptunghi :)
Titlul: Răspuns: 1128 Poligoane Scris de: cont cu nume gresit sau fals din Mai 27, 2011, 17:46:54 Citat Vi se pun T teste la dispoziţie. Pentru fiecare trebuie să afişaţi numărul de moduri în care se pot grupa beţele pentru a forma poligoane convexe regulate modulo un număr dat. 8)Titlul: Răspuns: 1128 Poligoane Scris de: Petru Trimbitas din Mai 27, 2011, 21:00:00 ma refeream la prima parte a enuntului
Titlul: Răspuns: 1128 Poligoane Scris de: cont cu nume gresit sau fals din Mai 27, 2011, 22:21:23 cu 6 betisoare iti desenez si 666013 poligoane neregulate distincte daca vreau (trebuie doar sa maresc/micsorez 2 unghiuri din hexagon) :P
ceea ce vreau sa zic este ca problema nu are sens daca poligoanele nu se considera regulate oricum in enunt se precizeaza sa fii atent la exemplu pentru a intelege mai bine cerinta nu cred ca in concurs ai fi busit solutia la problema asta pentru ca n-ai citit atent Titlul: Răspuns: 1128 Poligoane Scris de: UAIC.VlasCatalin din Octombrie 31, 2011, 10:42:03 Presupunem ca am gasit relatia de recurenta pentru matrice, dar acum cum trebue de procedat cu resturile diferite de fiecare data? ](*,)
Titlul: Răspuns: 1128 Poligoane Scris de: Simoiu Robert din Octombrie 31, 2011, 14:28:20 Cum adica cum ? Faci pt. fiecare test in parte o dinamica in O(N2), si asta e.
Titlul: Răspuns: 1128 Poligoane Scris de: UAIC.VlasCatalin din Octombrie 31, 2011, 14:58:28 Pai asta am si facut problema e ca asa imi intra in timp doar 6 teste, nustiu probabil e de la pascal :?
Titlul: Răspuns: 1128 Poligoane Scris de: Simoiu Robert din Octombrie 31, 2011, 15:07:26 Cred ca ar trebui marita limita de timp ...
Titlul: Răspuns: 1128 Poligoane Scris de: UAIC.VlasCatalin din Octombrie 31, 2011, 15:42:06 Cred ca este si alta solutie mai buna, in timp ce sunt surse cu timpi sub 200 ms si memorie in jur de 250Kb, poate sugereaza cineva dintre cei care au implimentat solutia buna, care e ideea :)
Titlul: Răspuns: 1128 Poligoane Scris de: Cristian Lambru din Octombrie 31, 2011, 19:59:36 Daca vorbesti de sursa mea sa stii ca am facut exact cum a zis si spiderman putin mai sus. Eu am folosit memorie O(N) facand dinamica pe vector. De aici probabil se mai poate scuti timpul deoarece alocarea memoriei cere mult timp :) .
Titlul: Răspuns: 1128 Poligoane Scris de: Mihai Visuian din Ianuarie 17, 2012, 16:49:56 Am o intrebare.
Se pune daca poligoanele sunt lipite? adica din 5 bete se pot face 2 triunghiuri sau e doar un patrulater cu diagonala :?:? Titlul: Răspuns: 1128 Poligoane Scris de: Dan H Alexandru din Martie 20, 2012, 11:10:26 Salut ! Nu ma prind care ar fi recurenta la aceasta problema. Sa posteze sau sa imi lase si mie un PM cine a rezolvat-o. Mi se pare ca e o dinamica O(N^2*T) , insa nu reusesc sa imi dau seama de recurenta. :aha:
LE: Mi-am dat seama. Hint: Construiti tabelul dinamic de la dreapta la stanga :thumbup: @ Mihai: Pentru 5 rezultatul e 1 (pentagonul). |