|
•andrei.12
|
 |
« : Aprilie 10, 2011, 10:51:19 » |
|
Aici puteti discuta despre problema Poligoane. |
|
|
|
|
Memorat
|
|
|
|
|
•soriyn
|
|
« Răspunde #1 : Aprilie 10, 2011, 12:42:29 » |
|
Imi da si mie cineva o idee de rezolvare ?  |
|
|
|
|
Memorat
|
|
|
|
|
•SpiderMan
|
|
« Răspunde #2 : 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.
|
|
|
|
« Ultima modificare: Aprilie 12, 2011, 08:53:40 de către Simoiu Robert »
|
Memorat
|
|
|
|
|
•S7012MY
|
|
« Răspunde #3 : Mai 27, 2011, 17:41:28 » |
|
Cred ca ar trebui pus poligoane convexe regulate pt ca pt n=6 poti forma si un dreptunghi  |
|
|
|
|
Memorat
|
|
|
|
•Magnus
Client obisnuit
Karma: 0
 Deconectat
Mesaje: 57
|
|
« Răspunde #4 : Mai 27, 2011, 17:46:54 » |
|
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.  |
|
|
|
|
Memorat
|
|
|
|
|
•S7012MY
|
|
« Răspunde #5 : Mai 27, 2011, 21:00:00 » |
|
ma refeream la prima parte a enuntului
|
|
|
|
|
Memorat
|
|
|
|
•Magnus
Client obisnuit
Karma: 0
Deconectat
Mesaje: 57
|
|
« Răspunde #6 : 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)  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 |
|
|
|
|
Memorat
|
|
|
|
|
•ctlin04
|
|
« Răspunde #7 : 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? |
|
|
|
|
Memorat
|
|
|
|
|
•SpiderMan
|
|
« Răspunde #8 : Octombrie 31, 2011, 14:28:20 » |
|
Cum adica cum ? Faci pt. fiecare test in parte o dinamica in O(N2), si asta e.
|
|
|
|
|
Memorat
|
|
|
|
|
•ctlin04
|
|
« Răspunde #9 : 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  |
|
|
|
|
Memorat
|
|
|
|
|
•SpiderMan
|
|
« Răspunde #10 : Octombrie 31, 2011, 15:07:26 » |
|
Cred ca ar trebui marita limita de timp ...
|
|
|
|
|
Memorat
|
|
|
|
|
•ctlin04
|
|
« Răspunde #11 : 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 |
|
|
|
|
Memorat
|
|
|
|
|
•maritim
|
|
« Răspunde #12 : 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 . |
|
|
|
|
Memorat
|
|
|
|
|
•VisuianMihai
|
|
« Răspunde #13 : 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  ? |
|
|
|
|
Memorat
|
|
|
|
|
•danalex97
|
|
« Răspunde #14 : 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.  LE: Mi-am dat seama. Hint: Construiti tabelul dinamic de la dreapta la stanga  @ Mihai: Pentru 5 rezultatul e 1 (pentagonul). |
|
|
|
« Ultima modificare: Martie 20, 2012, 19:38:12 de către Dan Alexandru »
|
Memorat
|
|
|
|
|
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena