782 Densitate

[•andreirulzzz]

problema se poate rezolva foarte usor cu ciurul... ordinea de idei este urmatoarea:

-ciurul pe 500.000 numere;
-calculezi intr-un vector "v" cate valori prime ai pana la numarul i<=n;
-citesti din fisierul de intrare testele, pe rand si afisezi v[prima val citita]-v[a 2-a val citita];

sper sa va ajute 

[•Anamaria20]

Am rezolvat si eu problema folosind ciurul dar imi iese din timp la ultimul test. Ce optimizari as putea sa fac ca sa iau 100?   

[•rusu_radu]

Intrebare: Trimit o sursa la aceasta problema si uraaaaaaaaaaaaa 100 de pct, trimit aceeasi sura peste 10 minute is bau 90 de pct (TLE la ultimu test)... nu vi se pare suspect.... lamuritzima:D

[•Marius]

Intrebare: Trimit o sursa la aceasta problema si uraaaaaaaaaaaaa 100 de pct, trimit aceeasi sura peste 10 minute is bau 90 de pct (TLE la ultimu test)... nu vi se pare suspect.... lamuritzima:D

Ultimul test îţi intră în timp la limită. Dacă mai optimizezi puţin programul vei lua 100 tot timpul.

[•miculprogramator]

Am citit topicul si am gasit multe idei bune aici. Am decis sa fac astfel: cu un ciur aflu cate numere prime sunt de la 1 pana la N, apoi intr-un vector x trebuie sa am ceva d egenul x[ i ]= cate numere prime sunt de la 1 pana la N. Adica sa fac un ciur( i ).

Ciurul arata asa:

Cod:

long ciur(long n)
{
     int i,j;
     for (i=2;i<=n;i++)
         prim[i]=1;
     for (i=2;i<=n;i++)
         if (prim[i])
          {
          nr++;
          for (j=i+i;j<=n;j+=i)
              prim[j]=0;
          }
     return nr;
}

Iar functia o apelez astfel: 

Cod:

for (i=1;i<=N;i++)
        x[i]=ciur(i); 

Problema este ca numerele din x nu sunt cele necesare, unde gresesc ? 

[•sima_cotizo]

Reinitializezi nr la 0 din cand in cand?

Oricum, (nu mai stiu rezolvarea problemei, dar...) de ce apelezi ciur de N ori? Poti sa-l faci o data (apelezi ciur(N)) si, daca tot ai un for de la 1 la N, sa numeri cate numere prime ai intalnit pana la un moment dat.

[•miculprogramator]

Pai apelez la ciur de n ori pentru a calcula cate nr prime am de la 1 la i . Ciurul imi returneaza cate numere prime am de la 1 pana la ce numar vreau eu, in cazul meu i.

N-am priceput exact ce ai vrut sa zici, as putea posta cod sa ne lamurim mai repede. Daca am permisiunea ... (stiu ca nu prea se da voie). Thanks for the answer !

Edit: Aaaa,cred ca m-am prins ! Ar trebui mai degraba sa retin in vector ce valori prime am pana la n si apoi sa afisez x[a]-x[ b ]. Asa ? 

[•jupanubv92]

    Rezolva mai intai problema de la arhiva educationala cu ciuru si o sa iti dai seama cum sa modifici ciuru ca sa nu fi nevoita sa il apelezi de n ori .
    Dupa ce ti-ai construit vectoru ala ca in mesaju care mi l-ai trimis , dar de data asta eficient , trebuie sa afisezi x[ b ]-x[ a-1 ] ci nu x[ a ]-x[ b ] .
    Sper ca te-am ajutat alta data incearca sa studiezi mai mult mesajele precedente de pe forum pentru ca s-au dat foarte multe indicatii de rezolvare la problema asta .

LE: Se pare ca pe pagina a doua am postat codu pentru ciur , mai trebuie doar sa afisezi x[ b ]-x[ a-1 ].
LEE: Sursa trimisa de tine prin PM nu este completa si nu se vede toata iar din cauza asta nu am putut sa vad cum ai facut tu ciuru.

[•sima_cotizo]

Pai apelez la ciur de n ori pentru a calcula cate nr prime am de la 1 la i . Ciurul imi returneaza cate numere prime am de la 1 pana la ce numar vreau eu, in cazul meu i.

N-am priceput exact ce ai vrut sa zici, as putea posta cod sa ne lamurim mai repede. Daca am permisiunea ... (stiu ca nu prea se da voie). Thanks for the answer !

Pana sa rezolvi problema optim, sa iti zic de ce, in parerea mea, nu functioneaza codul. Tu ai ceva care arata asa:

Cod:

long ciur(long n)
{
     int i,j;
     for (i=2;i<=n;i++)
         prim[i]=1;
     for (i=2;i<=n;i++)
         if (prim[i])
          {
          nr++;
          for (j=i+i;j<=n;j+=i)
              prim[j]=0;
          }
     return nr;
}

Iar functia o apelez astfel: 

Cod:

for (i=1;i<=N;i++)
        x[i]=ciur(i); 

In functia ciur, eu nu prea vad variabila "nr" reinitializata la 0. Cred ca pe masura ce apelezi ciur, valorile x[ i ] sunt din ce in ce mai mari (strict crescator)... asta e de la reinitializarea uitata Incearca asa:

Cod:

long ciur(long n)
{
     int i,j;
     nr = 0;                    // ! atentie aici
     for (i=2;i<=n;i++)
         prim[i]=1;
[... etc]
     return nr;
}

Sper ca nu gresesc si ca nu e altundeva problema.

[•miculprogramator]

Am creat alt ciur. In x pun nr prime de la 1 la N. Apoi afisez x[ b ]-x[ a-1].
Ciurul este:

Cod:

for(int i=2;i<=N;i++) 
          x[i]=1;
  for(int i=2;i*i<=N;i++)
    if(x[i]==1) for(int j=2;j*i<=N;j++) x[i*j]=0; 
  for(int i=2;i<=N;i++) 
            if(x[i]==1) cout<<i<<' '; 

Are si afisare. Nu pricep de ce nu imi arata bine afisarea finala,ceea ce trebuie sa obtin. Fac asa:

Cod:

 for (j=1;j<=Q;j++)
      {
      f>>a>>b;
      cout<<x[b]-x[a-1]<<endl;
      }

Daca am pus prea mult cod, sterg dupa. Mersi pentru ajutor.

[•jupanubv92]

Se pare ca nu prea ai inteles ce vrea problema de la tine . In primul rand n-ai cum sa afisezi x[ b ] - x[ a-1 ] cand tu in x ai valori de 0 si 1 . Din codul care l-ai postat eu inteleg ca tu pe x[ i ] retii 1 daca i este numar prim si 0 daca nu . In al doilea rand ca sa potzi sa afisezi x[ b ] - x[ a-1 ] trebuie ca pe pozitia x[ i ] sa fie numarul de numere prime din intervalul 1..i . Incearca sa intelegi ce vrea problema de exemplu daca tu stii cate numere prime exista de la 1 la a si de la 1 la b ca sa afli cate numere prime sunt intre a si b (b>=a) tot ce tre sa faci este sa afisezi  diferenta dintre numarul de numere prime al extremitatilor (a,b) .
    Mai concret daca in vectorul x reti numarul de numere prime pana la i (1..i..n) vectorul o sa arate asa : x[1]=0 x[2]=1 x[3]=2 x[4]=2 x[5]=3 x[6]=3 x[7]=4 x[8]=4 x[9]=4 x[10]=4 ....., iar daca iti cere sa afisezi cate numere prime sunt intre 1 si 10 afisezi x[10]-x[0] = 4 daca iti cere intre 3 si 7 afisezi x[7]-x[2] = 3 (daca de la 1 la 2 exista un numar prim , iar de la 1 la 7 exista 4 numere prime e logic ca intre 3 si 7 vor fi 3 ) .
    Sper ca ai inteles ..
   

[•miculprogramator]

Am prins ideea, dar nu-mi dau seama cum sa fac sa bag in x nr de nr prime de la 1 pana la i . Trebuie sa apelez cirul de N ori si mai trebuie sa fac si alt ciur. Incerc cum mi-a spus cotizo.

[•jupanubv92]

Incearca cum a spus cotizo , dar nu stiu daca o sa intre in timp . Dupa ce faci asa poti sa te uiti la posturile anterioare de la problema si o sa vezi cum potzi sa faci si fara sa apelezi de n ori.

[•miculprogramator]

Ce am incercat cu ciurul lui cotizo:

Cod:

nr=ciur(N);
    cout<<"nr="<<nr;
    for (i=1;i<=nr;i++)
        x[i]=ciur(i);

Imi da bine cate numere sunt intre 1 si N, dar nu se intampla nimic cu x[ i ].
Ma gandesc sa incerc altfel: intr-un vector v pun numerele prime de la 1 la N, vectorul asta va avea dimens nr. Si ca sa aflu x[ i ] iau i la la 1 la N si verific daca i==v[ j ], daca este egal il numar si dupa ce termin de numarat, bag ce am obtinut in x [ i ].

Nu cred insa ca intra in timp. Se poate mai simplu ? 

[•jupanubv92]

  Pai nu ai incercat bine . Tu lui nr ii dai la inceput ciur(N) iar nr va fi numarul de nr prime din intervalul [1,N] iar cand iti construiesti vectorul x tu mergi pana la nr si de aia nu se intampla nimic cu x[ i ] , daca o sa faci for-ul pana la N x[ i ] o sa fie bun .

PS : daca vrei sa faci mai simplu uitete la paginile anterioare si o sa vezi ca am postat varianta de ciur cea mai simpla , e buna si solutia care vrei sa o faci dar probabil vrei obtine 50% din punctaj.

LE : offtopic incearca sa nu mai postezi asa de des pe forum la fiecare problema pe care o rezolvi am vazut ca ai vreo 10 probleme facute si 227 de mesaje , la unele probleme daca nu reusesti sa le dai de cap potzi gasi rezolvarea doar citind cateva mesaje de pe forum . Este doar un sfat asa faceam si eu pe la inceput si au auzit impresia mai multor oameni ,care imi tot raspundeau la mesaje ,acum dupa vreo 2 ani si credema se saturase de mine .

[•sima_cotizo]

Ptr N-uri acceptabil de mari eu as face sa pun in X[ i ] "numarul de nr prime mai mici ca i" ceva de genul:

Cod:

long ciur(long n) {
	int i,j;
	nr = 0;
	for (i=2;i<=n;i++)
		este_prim[i]=1;
	for (i=2;i<=n;i++) {
		if (este_prim[i]==1) {
			nr++;
			for (j=i+i;j<=n;j+=i)
				este_prim[j]=0;
		}
		X[i] = nr;
	}
	return nr;
}

Apelezi o singura data functia ciur(N) si ai vectorul X[ i ] gata. Complexitatea este O(N^2) (sau p-acolo ). Bineinteles, am folosit o varianta de ciur mult simplificata, pe aceeasi idee poti sa mergi cu un ciur mai "complicat" (citeste articolul asta).

Cred ca repet, dar: nu am citit problema si nu m-am gandit cum as rezolva-o de fapt, dar incerc sa-ti dau indicatii pe ideea ta. Poti sa fii si tu creativa si sa incerci diverse combinatii intre ciurul din articol si o cautare binara pentru a determina cate nr prime sunt mai mici ca i ( hint : tii un vector de numere prime )

[•miculprogramator]

Am reusit sa scot 30 de puncte pe ea. Multumesc pt raspunsuri jupanului si lui cotizo. O sa ma mai chinui la ea o vreme, o sa gandesc singura. Doar daca ma impiedic tare mai intreb de ea.

O sa incerc si cu ciurul nou, poate si cautare binara. Thanks a lot. 

[•emilianparaicu14]

Iau Killed by Signal la ultimele 5 teste, si sunt destul de sigur ca nu sunt probleme de memorie, stie cineva de ce?
Later Edit: Se pare ca aveam probleme cu memoria, ciurul meu genera numere prea mari(nu pusesem i*i<=n ci doar i), acum am luat 100pct:).

[•Bit_Master]

Eu fac cu totul altfel.
Eu imi pun numerele prime intr-un vector folosind un ciur (unul dupa altul) si apoi caut binar in vector numerele, scazand indicii la care ii gasesc.  

___________________________________Mai tarziu________________________________________________

Am facut si cu metoda populara...

O mica greseala in textul problemei: a, b < N in cerinta, a ≤ b ≤ N la restrictii.

[•Horica]

cum se poate sa iau cu exact aceeasi sursa 80 si peste un minut 90?

[•wefgef]

Sursa ta este chiar la limita si astfel poti obtine punctaje diferite la rulari succesive.

[•Flameingo]

daca fac citire/afisare cu streamuri imi intra in timp la toate dar daca fac citire standard imi da TLE pe ultimul

[•iulius312]

Salut, am facut si eu codul folosind o functie cu ciurul pe cele N numere, schimband insa for( k=2;k*i<=N;k++) cu  for( k=i;k*i<=N;k++) ca sa nu mai am situatiile de genul 2*3 apoi 3*2, insa iau decat 30 de puncte. Daca pun for-ul de la k=2 iau 30 , restul TLE, iar daca pun for-ul de la k=i iau 30 si de la testul 5 in colo Killed by signal 11. aveti vreo idee cum sa reduc timp sau sa fac anumite imbunatatiri ? *vectorul de sume cumulate si cel de marcare cu 1 si 0  sunt definiti pana la 500001*