•wefgef
|
|
« : Decembrie 14, 2008, 14:34:18 » |
|
Aici puteti discuta despre problema Densitate.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•catalin93
Strain
Karma: 0
Deconectat
Mesaje: 13
|
|
« Răspunde #1 : Decembrie 14, 2008, 23:02:03 » |
|
Am si eu o problema cu sursa mea... ideea e ca TLE nu da ... numerele sunt pana la 500.000 ceea ce inseamna ca intra in int... si totusi nu imi da... as avea si eu nevoie de un sfat pentru ca am incercat teste gasite pe net cand am cautat teorema numerelor prime "Number of primes < 10^n. 0, 4, 25, 168, 1229, 9592, 78498," exact asa imi da... unde gresesc?
|
|
« Ultima modificare: Decembrie 14, 2008, 23:53:08 de către Paul-Dan Baltescu »
|
Memorat
|
|
|
|
•crus
Strain
Karma: 3
Deconectat
Mesaje: 44
|
|
« Răspunde #2 : Decembrie 14, 2008, 23:07:52 » |
|
cred ca trebuie sa afisezi x [ b ] - x [ a-1 ] ...
|
|
|
Memorat
|
|
|
|
•catalin93
Strain
Karma: 0
Deconectat
Mesaje: 13
|
|
« Răspunde #3 : Decembrie 14, 2008, 23:16:25 » |
|
de ce? ca fii atent... am editat foru asa... for(i=1;i<=q;++i) { scanf("%d%d",&a,&b); s = x[b] - x[a]; if((c[a] == false) || (c[b] == false) ) s++; printf("%d\n",s); } ca am citit pe celalat topic ca in cazul in care capetele sunt prime se iau si ele in calcul ... si acum am dat toate testele care mi-au trecut prin cap si da bine... unde gresesc? cred ca trebuie sa afisezi x [ b ] - x [ a-1 ] ...
daca reusesti sa-mi explici de ce rationamentu meu lua 0 puncte si ceea ce mi-ai zis tu sa schimb ia 100 iti ridic statuie [edit] nu posta de 2 ori consecutiv, foloseste butonul de editare a mesajului
|
|
« Ultima modificare: Decembrie 15, 2008, 21:15:33 de către Sima Cotizo »
|
Memorat
|
|
|
|
•crus
Strain
Karma: 3
Deconectat
Mesaje: 44
|
|
« Răspunde #4 : Decembrie 14, 2008, 23:19:33 » |
|
pai, ideea e urmatoarea...tu retii in x[ i ] cate numere prime ai intre 1 si i deci intre a si b ai un numar de numere prime egal cu x [ b ] care este numarul de prime in intervalul [1,b] din care scazi x [ a-1 ], care este egal cu numarul de numere prime din intervalul [1,a-1], si raman numerele prime din intervalul [a,b]. Tu facand operatia x [ b ] - x [ a ] calculai numarul de numere prime din intervalul [a+1,b]
|
|
« Ultima modificare: Decembrie 15, 2008, 21:15:47 de către Sima Cotizo »
|
Memorat
|
|
|
|
•catalin93
Strain
Karma: 0
Deconectat
Mesaje: 13
|
|
« Răspunde #5 : Decembrie 14, 2008, 23:42:09 » |
|
aaa... e logic mersi mult inca odata pentru ajutor apropo... acu eu ar trebui sa scot sursa din primul mesaj sau cu ajutorul a ceea ce ai zis tu toti o sa ia 100 nu?
|
|
|
Memorat
|
|
|
|
|
•crus
Strain
Karma: 3
Deconectat
Mesaje: 44
|
|
« Răspunde #7 : Decembrie 15, 2008, 21:01:25 » |
|
|
|
|
Memorat
|
|
|
|
•Tamasionutz
Strain
Karma: 1
Deconectat
Mesaje: 3
|
|
« Răspunde #8 : Decembrie 16, 2008, 16:21:51 » |
|
Ciurul lui Eratosthenes nu e suficient de rapid ?? Am incercat cu asta si mi-au iesit 40 puncte, la restul mi-a dat "Time limit exceeded" ... Am vrut si eu sa fac asa, adica sa calculez pentru fiecare numar cate nr prime se afla intre 1 si el, dar am considerat-o mai inceata decat ciurul. E mai inceata sau mai rapida (inca nu am inteles bine complexitatile si optimizarile, dar invat pe parcurs ) ....
|
|
|
Memorat
|
|
|
|
•c_e_manu
|
|
« Răspunde #9 : Decembrie 16, 2008, 16:42:46 » |
|
cand ai nevoie de mai multe numere, ciurul isi face foarte bine treaba... doar ca aici nu ai nevoie doar de ciur...trebuie sa-ti mai dai seama de ceva... dar numerele prime tot cu ciurul le calculezi... daca nu te descurci poti sa te uiti in articolul cu solutii
|
|
|
Memorat
|
|
|
|
•Mishu91
|
|
« Răspunde #10 : Decembrie 16, 2008, 16:49:34 » |
|
daca nu te descurci poti sa te uiti in articolul cu solutii Unde se poate gasi?
|
|
|
Memorat
|
|
|
|
•c_e_manu
|
|
« Răspunde #11 : Decembrie 16, 2008, 17:00:03 » |
|
|
|
|
Memorat
|
|
|
|
•SilverMoon
Strain
Karma: -9
Deconectat
Mesaje: 9
|
|
« Răspunde #12 : Decembrie 16, 2008, 18:40:24 » |
|
cand ai nevoie de mai multe numere, ciurul isi face foarte bine treaba... doar ca aici nu ai nevoie doar de ciur...trebuie sa-ti mai dai seama de ceva... dar numerele prime tot cu ciurul le calculezi... daca nu te descurci poti sa te uiti in articolul cu solutii Da, adica faci preprocesare si trimiti sursa cu un vector v[500000], unde v[i ] = nr de nr prime pana la i. Cu asta ai rezolvat problema in O(n). Bad point: sursa cam mare (multi KB), s-ar putea sa n-o primeasca.
|
|
« Ultima modificare: Decembrie 16, 2008, 18:42:15 de către Bogdan Tataroiu »
|
Memorat
|
|
|
|
•c_e_manu
|
|
« Răspunde #13 : Decembrie 16, 2008, 18:55:54 » |
|
Da, adica faci preprocesare si trimiti sursa cu un vector v[500000], unde v[i ] = nr de nr prime pana la i. Cu asta ai rezolvat problema in O(n). Bad point: sursa cam mare (multi KB), s-ar putea sa n-o primeasca. rezolvarea dn articol se refera la o preprcesare a vectorului inainte de a intra in ciclu de q teste, nu o preprocesare a intregului vector, folosind un alt program.
|
|
|
Memorat
|
|
|
|
•Florian
|
|
« Răspunde #14 : Decembrie 16, 2008, 20:54:58 » |
|
Eu am facut problema generand intr-un vector numerele prime prin intermediul ciurului. Apoi am aplicat doua cautari binare in vectorul de numere prime, pt fiecare pereche (a,b). A intrat fara probleme.
|
|
|
Memorat
|
|
|
|
•catalin93
Strain
Karma: 0
Deconectat
Mesaje: 13
|
|
« Răspunde #15 : Decembrie 16, 2008, 23:22:37 » |
|
ideea cea mai simpla dupa parerea mea e cea pe care am discutat-o la inceput... faci un vector de rezultate (int) in care pui nr de numere prime pana la nr curent... chiar daca numarul este compus spre ex : i = 10 v[10] = 4 i= 11 v[11] = 5 e simplu si dupa calculezi cate numere sunt in interval ca daca faci doar ciur testele sunt date smecher.. te pune sa calculezi intre 1 si 11 si dupa 1 si 12.. 1 si 13.. si tot asa... si asa da TLE
|
|
|
Memorat
|
|
|
|
•Florian
|
|
« Răspunde #16 : Decembrie 17, 2008, 11:36:45 » |
|
ideea cea mai simpla dupa parerea mea e cea pe care am discutat-o la inceput... faci un vector de rezultate (int) in care pui nr de numere prime pana la nr curent... chiar daca numarul este compus spre ex : i = 10 v[10] = 4 i= 11 v[11] = 5 e simplu si dupa calculezi cate numere sunt in interval ca daca faci doar ciur testele sunt date smecher.. te pune sa calculezi intre 1 si 11 si dupa 1 si 12.. 1 si 13.. si tot asa... si asa da TLE Nu ai inteles ce am spus. Eu nu fac ciur pt fiecare pereche de numere (a,b) ci fac ciur doar odata, la inceput, intre 1 si n. Iar intr-un vector retin numerele prime intre 1 si n. Acesta este vectorul pe care fac apoi cautarile binare.
|
|
|
Memorat
|
|
|
|
•Pepelea_Flaviu
Client obisnuit
Karma: 30
Deconectat
Mesaje: 98
|
|
« Răspunde #17 : Decembrie 17, 2008, 15:39:54 » |
|
merge si fara cautari binare
|
|
|
Memorat
|
|
|
|
•Florian
|
|
« Răspunde #18 : Decembrie 17, 2008, 16:35:18 » |
|
merge si fara cautari binare
Nu zice nimeni ca nu merge si fara. Eu doar am prezentat o alta metoda de rezolvare.
|
|
|
Memorat
|
|
|
|
•gabor_oliviu1991
|
|
« Răspunde #19 : Decembrie 17, 2008, 16:52:17 » |
|
am si eu o intrebare...eu in concurs am facut o rezolvare mai putin ortodoxa si am preprocesat toate nr prime si leam bagat intr-un vector. ideea e ca sursa mea depaseae 256 de kb si nu ma lasa sa o trimit...bine, am mai scos din numere si pana la urma am scos 50 de puncte (TLE, nu am facut cautarea binara ). va rog sa imi ziceti daka as putea "inghesui" toate numerele prime...care sunt aprox. 47 000 fara ca sursa mea sa depaseasca 256 kb....merci anticipat
|
|
|
Memorat
|
|
|
|
•Pepelea_Flaviu
Client obisnuit
Karma: 30
Deconectat
Mesaje: 98
|
|
« Răspunde #20 : Decembrie 17, 2008, 17:30:01 » |
|
dc nu ai calculat in acelasi program cu ciuru numerele prime.....ti s-a parut mai simplu sa bagi direct in sursa?
|
|
|
Memorat
|
|
|
|
•gabor_oliviu1991
|
|
« Răspunde #21 : Decembrie 17, 2008, 17:35:58 » |
|
pe moment am avut si ideea de ciur dar am zis ca incerc cu preprocesare ca sigur scot maxim...da nu o fost asa...ce sa zic...dupa concurs am rezolvat-o cu ciur si acum ma intreb daka merge si cu preprocesare
|
|
|
Memorat
|
|
|
|
•c_e_manu
|
|
« Răspunde #22 : Decembrie 17, 2008, 17:48:37 » |
|
sunt 41539 de nr prime... cel putin eu asa am gasit ... probabil s-a gandit si la faptul ca va economisi un timp destul de mare, daca nu mai foloseste ciurul...
|
|
|
Memorat
|
|
|
|
•Mishu91
|
|
« Răspunde #23 : Decembrie 17, 2008, 18:03:08 » |
|
Avand in vedere ca N < 5 * 105, iar complexitatea ciurului e aproape O(N) (v. postul de pe blog), formarea ciurului nu mananca foarte mult timp
|
|
|
Memorat
|
|
|
|
•gabor_oliviu1991
|
|
« Răspunde #24 : Decembrie 17, 2008, 18:09:14 » |
|
am inteles ca ciurul e cea mai buna idee dar ce intreb eu e cu totul altceva... pot pune 41 si cate zice manu de nr prime in vector fara ca sursa mea sa depaseasca 256 de kbs?
P.S: am vazut ca ciurul nu manca mult timp ca pana la urma am luat 100 pe ea. dar cu preprocesare pot scoate 100?
|
|
|
Memorat
|
|
|
|
|