Pagini: [1] 2   În jos
  Imprimă  
Ajutor Subiect: 169 Divizori Primi  (Citit de 15907 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
ditzone
Vizitator
« : Ianuarie 21, 2006, 17:05:00 »

Aici puteţi discuta despre problema Divizori Primi.
Memorat
badpanda
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 2



Vezi Profilul
« Răspunde #1 : Ianuarie 24, 2006, 18:36:39 »

Ma poate ajuta si pe mine cineva la problema asta?Folosesc ciurul lui Eratostene pentru a afla numarul de divizori primi,il calculez intr-un vector  si apoi parcurg vectorul de la sfarsit si ma opresc cand gasesc un numar care are numarul de divizor=k.Nu obtin decat 15 puncte...pe restu tle.Multumesc anticipat
Memorat

Nymphetamine, Nymphetamine...
ditzone
Vizitator
« Răspunde #2 : Ianuarie 24, 2006, 18:45:24 »

te poti uita peste solutia oficiala :

http://info.devnet.ro/articole.php?page=art&art=81&artpage=2
Memorat
mocke
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 19



Vezi Profilul WWW
« Răspunde #3 : Ianuarie 24, 2006, 22:46:24 »

incearca sa pregenerezi intr-o matrice solutiile...mat[nrdiv]=i
unde nrdiv=numarul de div ai lui i....copiezi in mat[j]->mat[i-1][j] dupa care actualizezi cu mat[nrdiv]=i! o sa ai raspuns pt test in O(1).
-nrdiv il calculezi folosindu-te de divizorii primi si de multiplii lui   Thumb up
Memorat

oricine greseste...nu oricine invatza
fireatmyself
Nu mai tace
*****

Karma: 36
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« Răspunde #4 : Ianuarie 25, 2006, 22:36:57 »

varule, nu mai posta idei din solutii oficiale ca facem o varza din topic-uri. cine nu stie sa rezolve si vrea solutii oficiale poate accesa pagina destinata exclusiv acestora. binecuvantate sunt insa hint-urile. sa nu intelegi gresit post-ul meu. nu vreau sa fie o apostrofare, ci doar un nevinovat comentariu  Mr. Green

btw. BADPANDA vad ca asculta COF Smile (ascultam si io prin tinerete, pana cand m-am dat pe blasfemiile lui Abath Smile. oricum tare "The Fire Still Burns" )
Memorat

Viata e scurta. Daca nu o putem lungi, macar s-o facem lata.
badpanda
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 2



Vezi Profilul
« Răspunde #5 : Ianuarie 25, 2006, 23:03:07 »

Abath n-am ascultat dar o sa caut si craddle e destul de fainutz......oricum...mie cel mai mult imi place children of boddom......mc mult pt atentionare ....nu observasem ca au aparut solutiile oficiale si incercam sa o fac singur....ma apuc acum de treaba poate iau 100 Very Happy Rock on
Memorat

Nymphetamine, Nymphetamine...
fireatmyself
Nu mai tace
*****

Karma: 36
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« Răspunde #6 : Ianuarie 25, 2006, 23:08:40 »

cu placere Smile (btw. Abath e solistul de la Immortal. intra pe http://www.metal-archives.com . aici gasesti toate trupele metal precum si informatii despre ele)
Memorat

Viata e scurta. Daca nu o putem lungi, macar s-o facem lata.
bogdan2412
Echipa infoarena
Nu mai tace
*****

Karma: 410
Deconectat Deconectat

Mesaje: 951



Vezi Profilul
« Răspunde #7 : Ianuarie 26, 2006, 08:57:27 »

O alta solutie asemanatoare cu cea oficiala: In timp ce se calculeaza vectorul de divizori primi, se poate tine o matrice de 8 linii, pe linia i fiind toate numerele cu exact i divizori primi sortate si apoi se poate caute cauta binar rezultatul. Am observat ca merge putin mai repede decat solutia oficiala.
Memorat
Tabara
Nu mai tace
*****

Karma: 20
Deconectat Deconectat

Mesaje: 216



Vezi Profilul
« Răspunde #8 : Martie 16, 2007, 22:59:25 »

Am implementat exact ca in solutia oficiala.Ori sunt acuma obosit si nu mai imi dau seama de ceea ce fac insa ... e o mica problema.

Am calculat acel sir ndp[] de 1 000 000 de numere.Iar matricea aia din cate am inteles eu si din cate vad, trebuie sa aiba 1 000 000 * 8 ....sau nu ?.Problema e ca fisierul meu .cpp are 3 Mb si nu mi-l trimite.Dar tot nu inteleg cum pot calcula matricea aia fara sa tin in actualul fisier si sirul ndp[]....
Poate sunt tampit si nu vad acuma ceva minor in abordare, dar chiar nu imi dau seama ce gresesc..

*programul meu compileaza foarte greu, dar imi da bine pe exemplu si ceva teste in plus.

..help !  sad
« Ultima modificare: Martie 16, 2007, 23:00:57 de către Tabara Mihai » Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #9 : Martie 17, 2007, 10:05:33 »

Nu poti trimite pe infoarena surse mai mari de 100 kb. Ideea e ca pregenerarea sa o faci la inceputul programului pe care il trimiti, nu sa folosesti o matrice de constante.
« Ultima modificare: Martie 17, 2007, 10:08:12 de către Paul-Dan Baltescu » Memorat

Am zis Mr. Green
Tabara
Nu mai tace
*****

Karma: 20
Deconectat Deconectat

Mesaje: 216



Vezi Profilul
« Răspunde #10 : Martie 17, 2007, 12:30:11 »

Nu poti trimite pe infoarena surse mai mari de 100 kb. Ideea e ca pregenerarea sa o faci la inceputul programului pe care il trimiti, nu sa folosesti o matrice de constante.

Mda..ai dreptate. Ok Nu stiu unde mi-a fost capul.
Am luat 100.

Multumesc inca o data. Embarassed
 Thumb up
« Ultima modificare: Martie 17, 2007, 13:01:47 de către Tabara Mihai » Memorat
kyrk
Strain


Karma: -8
Deconectat Deconectat

Mesaje: 13



Vezi Profilul
« Răspunde #11 : Martie 17, 2007, 18:21:34 »

ajutatzi-ma shi pe mine la problema asta..ca m-am umplut de nervi.. Brick wall !! calculez vectoru cu nr de div primi cu ciuru'..apoi fac o matrice in care memorez toate solutziile..exact ca in solutzia oficiala...chestia e ca teoretic ar trb sa am o matrice de 1 000 000 * 8 ..ceea ce nu imi intra in memorie ..iau ori SIGSEGV 11...ori un ok..nishte incorecturi...ca e matricea mica(in caz ca o mai micshorez..)shi iar SIGCEGV (http://infoarena.ro/job_detail/30246)  ..lasati-mi shi mie un emsaj...sau datzi-mi un add pe kyrk_dd pe mess...daca vretzi sursa Neutral  Brick wall
Memorat
astronomy
Nu mai tace
*****

Karma: 204
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« Răspunde #12 : Martie 17, 2007, 18:32:58 »

O matrice de 8*1.000.000 ocupa cam 32mb, deci iti intra in memorie.
Citat
11(SIGSEGV): Segmentation fault. Asta in 99% din cazuri inseamna ca ai probleme cu accesul la memorie. Ai iesit din limitele unui vector, ai facut stack overflow, etc.
Memorat
kyrk
Strain


Karma: -8
Deconectat Deconectat

Mesaje: 13



Vezi Profilul
« Răspunde #13 : Martie 17, 2007, 19:18:53 »

daca dau 8 * 200 000 merge pe juma din teste...daca dau 8 * 1 000 000 ...nu merge pe niciuna:|..care mah poate ajuta sa imi dea shi mie un add
Memorat
Tabara
Nu mai tace
*****

Karma: 20
Deconectat Deconectat

Mesaje: 216



Vezi Profilul
« Răspunde #14 : Martie 17, 2007, 22:13:15 »

daca dau 8 * 200 000 merge pe juma din teste...daca dau 8 * 1 000 000 ...nu merge pe niciuna:|..care mah poate ajuta sa imi dea shi mie un add

E ciudat.Mie mi-a intrat cu matrice de 1000000*8 si si acel sir ndp[] de 1000000.
Trimite-mi sursa pe mail, daca vrei, ca si mie azi dimineata mi-a iesit problema de 100 (  Eh? )

 Thumb up
Memorat
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #15 : Mai 01, 2007, 15:11:28 »

 Problema asta ma dispera!  Fighting Nu prea pricep cum sta treaba vu matricea aia. Nu`mi dau seama cum sa o formez intr`un mod optim. Am facut o implementare de 45 de puncte , folosind doar vectorul,  pe unele teste imi da TLE [ceea ce probbabil e normal, pt k nu am folosit matricea], insa pe testele 4-8(inclusiv) iau WA! Kiar nu pot sa `mi dau seama... Brick wall
Memorat
peanutz
Nu mai tace
*****

Karma: 10
Deconectat Deconectat

Mesaje: 296



Vezi Profilul
« Răspunde #16 : Mai 01, 2007, 17:08:59 »

sa zicem ca ai un vector cu semnificatia div[ i ] = nr de div primi a lui i...

formezi matricea dupa formula de recurenta:

matrice[ i ] = matrice[ i-1 ]

si ca sa ai optim mai schimbi matrice[ i ][ div[ i ] ] = i, adica pana la i cel mai mare numar cu div[ i ] divizori primi e chiar i, ceea ce e destul de logic Tongue
Memorat

....staind....
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #17 : Mai 01, 2007, 17:35:53 »

Dapz, ms de ajutor! O facusem insa inainte! Ma ajutase Mihai Tabara!  Ok
Memorat
05_Yohn
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 13



Vezi Profilul
« Răspunde #18 : Noiembrie 24, 2008, 21:08:57 »

care ma ajuta si p mn??.. am facut problema dupa ideea de la solutia oficiala.. ciur, matrice, afisare.. imi da Non-zero exit status.. Neutral .. initializez matricea si vectorii cu 0 la inceput..  sad habar n-am c sa-i mai fac..daca are cineva vreo idee..Neutral ..


ps: lucrez in pascal Neutral:|
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #19 : Noiembrie 25, 2008, 10:34:07 »

N este 1.000.000, nu 100.000 Smile. Schimba limitele si vei lua 100.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
05_Yohn
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 13



Vezi Profilul
« Răspunde #20 : Noiembrie 25, 2008, 19:04:53 »

da ai avut dreptate.. mersi ... am luat 100  Dancing
Memorat
vlasceanu
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 5



Vezi Profilul
« Răspunde #21 : Martie 24, 2009, 16:13:53 »

Am si eu o mica problema. Deci citesc toate numerele din fisier si in acelasi timp il retin pe cel mai mare dintre ele. Apoi Apelez Ciur(max) ca sa imi genereze vectorul cu numerele prime mai mici si egale decat max. Apoi generez vectorul ndp[] in felul urmator
Cod:
for(int i=2;i<=max+1;i++)
    {
      int aux=0;     
      for(int j=2;j<=i/2;j++)
      {
       if(ciur[j]==0 && i%j==0)
       {
        aux++;             
       }       
      }
      switch(aux)
      {                 
        case 1:
             {
               mat[i1][1]=i;
               i1++;         
             }
             break;
        case 2:
             {
               mat[i2][2]=i;
               i2++;         
             }
             break;
        case 3:
             {
               mat[i3][3]=i;
               i3++;         
             }
             break;
        case 4:
             {
               mat[i4][4]=i;
               i4++;         
             }
             break;
        case 5:
             
             {
               mat[i5][5]=i;
               i5++;         
             }
             break;
        case 6:
             {
               mat[i6][6]=i;
               i6++;         
             }
             break;
        case 7:
             {
               mat[i7][7]=i;
               i7++;         
             }
             break;
        case 8:
             
             {
               mat[i8][8]=i;
               i8++;         
             }
             break;                               
      }
    }
iar apoi caut solutia in matricea mat pentru fiecare pereche de numere n-k citite anterior. Problema este ca imi iese din timp cam cum 50ms pe majoritatea testelor + ca pe 2 deste imi da raspuns gresit. In final iau doar 10 puncte. Ma poate lamuri si pe mine cineva ce trebuie sa fac sa iau mai multe ca nu imi dau seama. Daca este nevoie de o parte mai mare de cod spuneti.10x anticipat
Memorat
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #22 : Martie 24, 2009, 16:23:07 »

Citeste topicul asta si , eventual, si solutia oficiala. Este destul de greu (+incomod) pentru cineva sa gaseasca greseli in programul tau. Spor!  Smile
Memorat
vlasceanu
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 5



Vezi Profilul
« Răspunde #23 : Martie 24, 2009, 16:25:05 »

Citeste topicul asta si , eventual, si solutia oficiala. Este destul de greu (+incomod) pentru cineva sa gaseasca greseli in programul tau. Spor!  Smile

Citisem tot si inainte. Cred ca imi iese din timp din cauza ca nu am folosit cautarea binara.
Memorat
Alexa_ioana_14
Strain
*

Karma: 6
Deconectat Deconectat

Mesaje: 37



Vezi Profilul
« Răspunde #24 : Iulie 08, 2009, 13:55:17 »

O alta solutie asemanatoare cu cea oficiala: In timp ce se calculeaza vectorul de divizori primi, se poate tine o matrice de 8 linii, pe linia i fiind toate numerele cu exact i divizori primi sortate si apoi se poate caute cauta binar rezultatul.

Pe ideea asta am mers si eu...doar ca iau 75 puncte Think. pe celelalte teste iau WA! Am luat si cazul n=1 sau k=0! Ma poate ajuta cineva sa scot sursa asta de 100 va rog?
Memorat
Pagini: [1] 2   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines