infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: ditzone din Ianuarie 21, 2006, 17:05:00

Titlul: 169 Divizori Primi
Scris de: ditzone din Ianuarie 21, 2006, 17:05:00

Aici puteţi discuta despre problema Divizori Primi (http://infoarena.ro/problema/divprim).

Titlul: 169 Divizori Primi
Scris de: Birca Dan din 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

Titlul: 169 Divizori Primi
Scris de: ditzone din Ianuarie 24, 2006, 18:45:24

te poti uita peste solutia oficiala :

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

Titlul: 169 Divizori Primi
Scris de: Barca Cristian Mihai din 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 :thumbup:

Titlul: 169 Divizori Primi
Scris de: Bogdan-Alexandru Stoica din 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 :mrgreen:

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

Titlul: 169 Divizori Primi
Scris de: Birca Dan din 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 :D Rock on

Titlul: 169 Divizori Primi
Scris de: Bogdan-Alexandru Stoica din Ianuarie 25, 2006, 23:08:40

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

Titlul: 169 Divizori Primi
Scris de: Bogdan-Cristian Tataroiu din 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.

Titlul: Răspuns: 169 Divizori Primi
Scris de: Tabara Mihai din 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:

Titlul: Răspuns: 169 Divizori Primi
Scris de: Paul-Dan Baltescu din 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.

Titlul: Răspuns: 169 Divizori Primi
Scris de: Tabara Mihai din Martie 17, 2007, 12:30:11

Citat din mesajul lui: Paul-Dan Baltescu din 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.

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

Multumesc inca o data. :oops:
:thumbup:

Titlul: Răspuns: 169 Divizori Primi
Scris de: Dragos Dumitrescu din Martie 17, 2007, 18:21:34

ajutatzi-ma shi pe mine la problema asta..ca m-am umplut de nervi.. ](*,) !! 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 :| ](*,)

Titlul: Răspuns: 169 Divizori Primi
Scris de: Airinei Adrian din 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.

Titlul: Răspuns: 169 Divizori Primi
Scris de: Dragos Dumitrescu din 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

Titlul: Răspuns: 169 Divizori Primi
Scris de: Tabara Mihai din Martie 17, 2007, 22:13:15

Citat din mesajul lui: Dragos Dumitrescu din 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

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 ( :-s )

:thumbup:

Titlul: Răspuns: 169 Divizori Primi
Scris de: Florian Marcu din 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... ](*,)

Titlul: Răspuns: 169 Divizori Primi
Scris de: Andrei Homorodean din 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 :P

Titlul: Răspuns: 169 Divizori Primi
Scris de: Florian Marcu din Mai 01, 2007, 17:35:53

Dapz, ms de ajutor! O facusem insa inainte! Ma ajutase Mihai Tabara! :ok:

Titlul: Răspuns: 169 Divizori Primi
Scris de: E1 La5c01 din 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.. :| .. initializez matricea si vectorii cu 0 la inceput.. :sad: habar n-am c sa-i mai fac..daca are cineva vreo idee..:| ..

ps: lucrez in pascal :|:|

Titlul: Răspuns: 169 Divizori Primi
Scris de: Andrei Grigorean din Noiembrie 25, 2008, 10:34:07

N este 1.000.000, nu 100.000 :). Schimba limitele si vei lua 100.

Titlul: Răspuns: 169 Divizori Primi
Scris de: E1 La5c01 din Noiembrie 25, 2008, 19:04:53

da ai avut dreptate.. mersi ... am luat 100 \:D/

Titlul: Răspuns: 169 Divizori Primi
Scris de: Vlasceanu Razvan din 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

Titlul: Răspuns: 169 Divizori Primi
Scris de: Florian Marcu din 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! :)

Titlul: Răspuns: 169 Divizori Primi
Scris de: Vlasceanu Razvan din Martie 24, 2009, 16:25:05

Citat din mesajul lui: Marcu Florian din 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! :)

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

Titlul: Răspuns: 169 Divizori Primi
Scris de: Antoche Ioana Alexandra din Iulie 08, 2009, 13:55:17

Citat din mesajul lui: Bogdan Tataroiu din Ianuarie 26, 2006, 08:57:27

Pe ideea asta am mers si eu...doar ca iau 75 puncte :-k. 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?

Titlul: Răspuns: 169 Divizori Primi
Scris de: Dragos Oprica din Iulie 10, 2009, 11:15:08

Citat din mesajul lui: Antoche Ioana Alexandra din Iulie 08, 2009, 13:55:17

Citat din mesajul lui: Bogdan Tataroiu din Ianuarie 26, 2006, 08:57:27

Pe ideea asta am mers si eu...doar ca iau 75 puncte :-k. 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?

Si eu am avut o greseala la cautarea binara si luam doar 80 puncte. ai grija daca numarul care il cauti este mai fie mai mic decat primul numar din sirul tau fi mai mare decat ultimul numar din sirul tau. Aici gresea cautarea mea. Sper sa fiu de folos :)

Titlul: Răspuns: 169 Divizori Primi
Scris de: A Cosmina - vechi din Iulie 18, 2009, 14:10:59

Salut !

Am intampinat o problema (http://infoarena.ro/job_detail/332539)...Imi spune ca am probleme cu fisierele,insa la mine pe calculator ruleaza si cred ca am lucrat cu fisierele cat se poate de normal:

Cod:

#include <fstream.h>
.....
ifstream f("divprim.in");
ofstream g("divprim.out");
.....
f>>t;
for (i=0;i<t;i++)
    f>>n[i]>>k[i];
f.close();
......
for (i=0;i<t;i++)
    g<<div[i]<<endl;
g.close();

N-am mai avut niciodata probleme de genul cand am trimis probleme.Teste facute de mine sunt si ele bune.

Ma poate ajuta cineva sa descopar ce s-a intamplat? :sad:

Titlul: Răspuns: 169 Divizori Primi
Scris de: Paul-Dan Baltescu din Iulie 18, 2009, 14:19:56

Ai inclus libraria <fstream.h.>.

Titlul: Răspuns: 169 Divizori Primi
Scris de: A Cosmina - vechi din Iulie 18, 2009, 14:24:12

Si nu trebuia? :-s
Eu asa stiu ca-i cu fisierele,ca le trebuie <fstream.h> ... Nu pricep ce ai vrut sa zici.

Titlul: Răspuns: 169 Divizori Primi
Scris de: Paul-Dan Baltescu din Iulie 18, 2009, 14:29:29

Ai un un punct in plus. Ala rosu.

Titlul: Răspuns: 169 Divizori Primi
Scris de: A Cosmina - vechi din Iulie 18, 2009, 14:46:39

Asa este,multumesc frumos.

Din pacate acum imi iese din timp... :-k

Am pus dimensiunile de 100 000.Trebuia de 1 000 000 ?

Titlul: Răspuns: 169 Divizori Primi
Scris de: Bogdan Vlad din Noiembrie 25, 2009, 18:09:22

:readthis: am preprocesat un vector de 1.000.000 de numere (pentru fiecare, nr de divizori primi)
si vad ca nu vrea sa-mi primeasca sursa.. are cam 2,8mb.. are ceva? :?

Titlul: Răspuns: 169 Divizori Primi
Scris de: Savin Tiberiu din Noiembrie 25, 2009, 22:13:55

Nu poti trimite surse mai mari de 256kb. E o masura luata tocmai pentru a combate astfel de chestii. Ar trebui sa faci problema cu un algoritm bun, nu preprocesand milioane de valori ;)

Titlul: Răspuns: 169 Divizori Primi
Scris de: FMI Romila Remus Arthur din Mai 30, 2010, 13:18:38

Nu inteleg de ce primesc WA pe peste 1,4-8 iar pe celelalte e ok.Sunt cazuri particulare ?

Titlul: Răspuns: 169 Divizori Primi
Scris de: Petenchea Alexandru din Noiembrie 26, 2011, 15:20:23

Ma miram de ce primesc doar 50 de puncte atunci cand folosesc clasele std::ifstream si std::ofstream. Cand am incercat cu functiile din cstdio am primit punctaj maxim. Stiam ca obiectele sunt mai incete decat functiile, dar nu am crezut ca exista chiar asa o mare diferenta :annoyed:
Sunt nou pe aici, este posibil sa imi downloadez un evaluator (de preferabil sa il pot folosi pe Ubuntu), sau programul e "interzis" concurentilor ? Ma intereseaza pentru ca mi-ar placea sa masor timpul de executie :)

Titlul: Răspuns: 169 Divizori Primi
Scris de: George Marcus din Noiembrie 26, 2011, 15:43:30

Eu am patit exact invers la o problema. Poate ne lamureste cineva si pe noi.
Nu cred ca exista un evaluator infoarena pe care sa il poti downloada.

Titlul: Răspuns: 169 Divizori Primi
Scris de: andreycurent din Decembrie 08, 2011, 15:53:11

Ar putea sa vina cineva cu o imbunatatire(exceptand solutia cu generare recurenta a matricei) la codul meu? Am facut ciur/cautare binara, dar iau 60 de puncte, TLE pe restul.

LE: Rezolvat

Titlul: Răspuns: 169 Divizori Primi
Scris de: Vlad Negura din Octombrie 24, 2015, 14:06:58

Pentru optimizare incercati sa folositi fopen(stiod.h) in loc de streamuri. ;)

Titlul: Răspuns: 169 Divizori Primi
Scris de: Birou Rares Gabriel din Martie 24, 2017, 18:00:00

Imi mai da cineva teste la aceasta problema?