ditzone
Vizitator
|
|
« : Decembrie 17, 2005, 14:51:16 » |
|
Aici puteţi discuta despre problema Descompuneri.
|
|
|
Memorat
|
|
|
|
•hitmann
Strain
Karma: 2
Deconectat
Mesaje: 14
|
|
« Răspunde #1 : Decembrie 21, 2005, 20:01:54 » |
|
in enunt nu se specifica nici o restrictie pt descompuneri de genu : pt n=36 descompunerea 1 * 36 si de aici am putea face 1*1*1*1*1*1*1...*1*1*1*36 presupun ca e o gresala, nu ?
|
|
|
Memorat
|
|
|
|
ditzone
Vizitator
|
|
« Răspunde #2 : Decembrie 21, 2005, 20:50:22 » |
|
Nu se specifica 1*36.. se specifica doar 36... Termenii sirului trebuie sa fie >1
|
|
|
Memorat
|
|
|
|
•hitmann
Strain
Karma: 2
Deconectat
Mesaje: 14
|
|
« Răspunde #3 : Februarie 24, 2006, 19:18:09 » |
|
se foloseste ciurul lui erathostene ?
|
|
|
Memorat
|
|
|
|
|
•pauldb
|
|
« Răspunde #5 : August 20, 2006, 10:29:38 » |
|
Am citit solutia oficiala. Nu inteleg cum se poate construi matricea respectiva in O(D^2 log D) [sau O(D^2)] daca fiecare divizor al lui N il inmultesc cu fiecare si daca rezultatul este tot un divizor al lui N atunci am de actualizat D numere. Mie mi se pare ca O(D^3)...Am inteles eu gresit sau se poate optimiza?
|
|
|
Memorat
|
Am zis
|
|
|
ditzone
Vizitator
|
|
« Răspunde #6 : August 25, 2006, 11:56:28 » |
|
Daca rezultatul este un divizor al lui N ai de actualizat o singura pozitie in matrice. (Sa zicem ca ai inmultit cu divizorul i si ai obtinut divizorul j .. vei actualiza doar A [ i ] [ j ] - adaugi aici valoarea din A [ i - 1 ] [ j / i ] )
|
|
« Ultima modificare: August 25, 2006, 13:11:41 de către domino »
|
Memorat
|
|
|
|
•peanutz
|
|
« Răspunde #7 : Iulie 20, 2007, 00:04:37 » |
|
Nu stiu ce se intampla cu solutia mea. Initial am implementat cautarea binara, dar am avut 7 TLE. Bun, apoi am facut cautarea aia liniara care se reia de la pasul precedent, la fel. Sunt destul de sigur ca am N^2... Am rulat si fara reconstituirea solutiei, e putin mai bine in ideea ca prind 4 teste. Parcurg matricea invers. Credeti ca daca as pune divizorii in ordine inversa si as parcurge normal ar merge mai rpd? Sugestii, va rog
|
|
|
Memorat
|
....staind....
|
|
|
|
•peanutz
|
|
« Răspunde #9 : Iulie 20, 2007, 13:28:21 » |
|
Aici nu parcurg chiar invers, liniile le parcurg normal, coloanele le parcurg invers. Oricum, la problema asta imi lua cam mult scoaterea divizorilor lui n .... acum incerc sa fac in O(sqrt(n)). Voi cum ati scos...? Ca eu fac ceva mai ciobanesc ce implica si o sortare la urma
|
|
|
Memorat
|
....staind....
|
|
|
•wefgef
|
|
« Răspunde #10 : Iulie 20, 2007, 15:08:51 » |
|
Daca un numar n se divide cu a, inseamna ca exista un numar b astfel incat a*b=n. Evident, cel putin unul din cele doua numere, a sau b, este <= cu sqrt(n). Astfel, trebuie doar sa afli toate numerele a intre 1 si sqrt(n) cu proprietatea ca n se divide cu a, ceilalti divizori fiind de forma n/a.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•danalex97
|
|
« Răspunde #11 : Aprilie 10, 2012, 17:44:06 » |
|
Cred ca trebuie marit putin timpul de executie. Incercati sa implementati problema sau trimiteti orice sursa care a luat 100. Eu am implementat-o si apoi am trimis o sursa de 100 ca sa vad dupa aceea unde am de optimizat si am constatat ca o sursa printre ultimele trimise care lua 100 acum ia doar 90.
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #12 : Aprilie 10, 2012, 20:07:14 » |
|
Ai dreptate. Am crescut limita la 0.5s.
|
|
|
Memorat
|
Am zis
|
|
|
•darren
Client obisnuit
Karma: 106
Deconectat
Mesaje: 76
|
|
« Răspunde #13 : Iunie 09, 2014, 11:46:16 » |
|
Cred ca testele la problema asta nu sunt prea bune (si nici solutia). Numarul cu cei mai multi divizori mai mic decat 10^12 este 963761198400, care are 6720 de divizori. Cam toate sursele isi declara limita sub acest numar. De asemenea, asa nu cred ca mai intra in memorie solutia cu O(D^2) memorie (si din cate vad toate sursele sunt pe aceasta solutie).
|
|
|
Memorat
|
|
|
|
|