782 Densitate

[•sima_cotizo]

Presupun ca faci un vector de constante. Ai putea incerca sa le scrii in hex (baza 16) pentru ca e posibil ca pentru unele numere sa folosesti mai putine caractere.

De asemenea poti incerca o codare in care fiecare numar sa il scrii ca pe un string, iar fiecare cifra sa o consideri un caracter intr-o baza aleasa de tine (100 de exemplu). Totusi, cred ca decodificarile ti-ar lua cam la fel ca ciurul...

[•Pepelea_Flaviu]

baga ciuru pe biti...ca apoi nu te mai gandesti tu ca mananca timp (uita-te in arhiva educationala ca pt 2 000 000 intra in 16 ms)).... incercati sa va descurcati si fara sa puneti un vector ca constanta.....nu arata grozav nici o sursa de 300 de kb.

[•gabor_oliviu1991]

merci pt raspunsuri;) un + la voi

[•Robybrasov]

merge foarte bine, dupa ciur, un arbore indexat binar sau unul de intervale pentru interogare

[•gabitzish1]

De ce se prefera solutii asa complicate cand solutia oficiala e foarte simpla? 

[•Robybrasov]

nu m-am uitat peste solutiile oficiale. a fost prima varianta care mi-a venit in cap, am implementat-o si a mers. poate ajuta totusi pe cineva si o asemenea abordare.

[•Bogdan_tmm]

Intre 7 si 20 se refera la intervalu (7,20)(logic) sau [7,20](ilogic).
e logic sau ilogic?)
Later: imi dadui seama ca e "ilogic"

[•shnako]

Ce are mai special testul 3 ? Imi da wrong answer pe el ... Am incercat daca a=b, daca a e minim si b e maxim, daca a sau b sunt prime. Ce caz particular am putut uita ?

[•razyelx]

Daca iti da WA pe testul 3 nu are cum sa fie de la limite. Cel mai sigur ca e la cautarea binara. Eu de exemplu nu am stiut sa fac cautarea binara foarte exacta, si dupa fiecare cautare verificam niste treburi. Dar zi cum ai facut tu.

[•shnako]

Asta e cautarea binara :

Cod:

long cbin (long w, bool e)
	{
   long x1, y1, mij;
   x1=1;
   y1=k;
   mij=(x1+y1)/2;
   while (x1<=y1)
   	{
      if (s[mij]<=w&&s[mij+1]>w&&e)
      	return mij;
      if (s[mij]>=w&&s[mij-1]<w&&!e)
      	return mij;   //Aici nuintra cand mij=2.
      if (w<s[mij])
      	y1=mij-1;
      else
      	x1=mij+1;
      mij=(x1+y1)/2;
      }
   }

Iar asta e bucata cu tiparirea :

Cod:

for (i=1;i<=q;i++)
	{
   if (i==3)
   	i=3;
   fscanf(f, "%ld%ld", &x, &y);
   if (x<=2&&y>=s[k])
   	{
      fprintf(g, "%ld\n", k);
      continue;
      }
   fprintf(g, "%ld\n", cbin(y, 1)-cbin(x, 0)+1);
   }

[•razyelx]

Mda... si eu avut aceeasi problema cu 2 parca. Dar Prindeam mai cazuri nasoale, pentru ca cautarea binara incrementa ceva in plus.
Oricum trebuie sa modifici afisarea, cum am facut si eu de altfel:

Cod:

         i=bs(a,1);  
         j=bs(b,2);  
  
         if(a == prime[i] && b != prime[j]){  
            fprintf(out,"%ld \n",j-i);  
          }  
  
  
           if(a != prime[i] && b == prime[j]){  
            fprintf(out,"%ld \n",j-i+1);  
          }  
   
          if(a == prime[i] && b == prime[j]){  
            fprintf(out,"%ld \n",j-i+1);  
          }  
  
          if(a != prime[i] && b != prime[j]){  
            fprintf(out,"%ld \n",j-i);  
          }

Oricum te prinzi tu care e faza din afisare ca esti cuprins de problema, eu am mai uitat sustele. Daca iti iese imi dai un ceai la scoala. 

[•shnako]

Nu e aia problema, ms oricum
Ideea e ca imi da bine pe orice test imi pot eu imagina... Se pare ca testul 2 e ceva caz particular ... Desi le-am incercat pe toate ... Alte idei ?

[•c_e_manu]

depinde de metoda ta...am vazut ca folosesti o cautare binara... descrie putin ce faci acolo... ce cauti binar? eu am rezolvat fara cautare binara, doar un ciur

[•razyelx]

frate... problema e la afisare. Pentru i-uri diferite, ai acelasi numar de numere prime. Acolo intervine omica problema la cautarea binara. Stiu ca mi-e nu imi dadea bine la unmoment dat nici pe exemplu pt b=19 sau b=20. La 19 cand se modfica(de la 18 se trece la 19 se mareste numarul de nr prime) nu iti returneaza ce vrei ca nu mai icnrementeaza, iar la 20 se va opri la 19. Ceva de genu era. bafta! daca nu iti iese. iti postez cautarea mea binara.

[•shnako]

Seba eu tot am incercat sa fac cum zici tu dar tot aia da. Deci am stat cu Manu C. 2 zile sa vedem ce are si pauza... Postez acum toata sursa (sper ca e ok) ca deja am facut gauri in tastatura.

Cod:

#include <stdio.h>
FILE *f, *g;
long k=0, s[45550], i, j, n, q, x, y, t;
bool v[500005];

long cbin (long w, bool e)
	{
   long x1, y1, mij;
   x1=1;
   y1=k;
   mij=(x1+y1)/2;
   while (x1<=y1)
   	{
      if (s[mij]<=w&&s[mij+1]>w&&e)
      	return mij;
      if (s[mij]>=w&&s[mij-1]<w&&!e)
      	return mij;  
      if (w<s[mij])
      	y1=mij-1;
      else
      	x1=mij+1;
      mij=(x1+y1)/2;
      }
   return mij;
   }

void ciur(void)
	{
   s[1]=2;
   k=1;
   for (i=3;i<=n;i+=2)
   	if (!v[i])
      	{
         s[++k]=i;
         if (i<=707)
      	for (j=i;i*j<=n;j++)
         	v[i*j]=1;
         }
   }

int main(void)
{
f=fopen("densitate.in", "r");
g=fopen("densitate.out", "w");
fscanf(f, "%ld%ld", &n, &q);
ciur();

for (i=1;i<=q;i++)
	{
   if (i==3)
   	i=3;
   fscanf(f, "%ld%ld", &x, &y);
   if (x<=2&&y>=s[k])
   	{
      fprintf(g, "%ld\n", k);
      continue;
      }    
   fprintf(g, "%ld\n", cbin(y, 1)-cbin(x, 0)+1);
   }
fcloseall();
return 0;
}

Culmea e ca pe sursa asta iau testu 2 dar e prea inceata

Cod:

#include <stdio.h>
#include <math.h>
FILE *f, *g;
long k=0, s[41550], i, j, n, q, x, y, t;
bool v[500001];

void ciur(void)
	{
   s[1]=2;
   k=1;
   for (i=3;i<=n;i+=2)
   	if (!v[i])
      	{
         s[++k]=i;
         if (i<=707)
      	for (j=i;i*j<=n;j++)
         	v[i*j]=1;
         }
   }

int main(void)
{
f=fopen("densitate.in", "r");
g=fopen("densitate.out", "w");
fscanf(f, "%ld%ld", &n, &q);
ciur();
for (i=1;i<=q;i++)
	{
   fscanf(f, "%ld%ld", &x, &y);
   for (j=1;j<=k;j++)
   	if (s[j]>=x)
      	break;
   t=j;
   for (;j<=k;j++)
   	if (s[j]>y)
      	break;
   fprintf(g, "%ld\n", j-t);
   }
fcloseall();
return 0;
}

Cineva ceva idei ? 

[•jupanubv92]

  Cred ca s-a mai spuns in posturile anterioare , dar iti mai spun si eu , ca sa iti intre in timp poti sa faci cu Ciurul lui Eratostene si fara cautare binara , iti ti un vector x [ i ] ( 1<=i<=n) in care pe pozitia x [ i ] iti reti cate numere prime exista de la 1 la i , iar pentru fiecare intrebare de genu :"cate numere prime sunt in intervalul a b " tu afisezi  x[ b ]-x[ a ]
    Vad ca sti sa faci ciurul lui eratostene  asa ca tot ce tre sa faci ca sa iei 100 e sa stergi cautarea binara si sa modifici un pic ciurul la ceva de genu :

Cod:

void ciur()
{
    x[1]=0;nr=1;
    for(int i=2;i<=N;i++)
      if(!fol[i])
       {
        x[++nr]=x[nr-1]+1;
        for(int k=2;k*i<=N;k++)
          fol[k*i]=1;
       }
       else x[++nr]=x[nr-1];

}

Sper ca te-am ajutat .

[•c_e_manu]

Cred ca s-a mai spuns in posturile anterioare , dar iti mai spun si eu , ca sa iti intre in timp poti sa faci cu Ciurul lui Eratostene si fara cautare binara , iti ti un vector x [ i ] ( 1<=i<=n) in care pe pozitia x [ i ] iti reti cate numere prime exista de la 1 la i , iar pentru fiecare intrebare de genu :"cate numere prime sunt in intervalul a b " tu afisezi  x[ b ]-x[ a ]
    Vad ca sti sa faci ciurul lui eratostene  asa ca tot ce tre sa faci ca sa iei 100 e sa stergi cautarea binara si sa modifici un pic ciurul la ceva de genu :...

vlad a intrebat daca stie cineva care e problema la varianta lui... nu a cerut alta varianta... se intra in timp si folosind cautare binara... doar ca mai trebuie slefuita putin ca primeste un WA pe care nu a reusit sa il corecteze... probabil e ceva caz particular ce nu-l prinde... eu nu l-am gasit... poate il stie altcineva ce a folosit varianta asta...

PS: nu inteleg de ce in momentul in care se incearca alta varianta de rezolvare veniti toti si repetati solutia oficiala de la problema??!!

[•gabor_oliviu1991]

defapt pt metoda aia trebuie sa afisezi x[ b ] - x[ a -1 ] ca poate pe pozitia a ai un numar prim. + ca am aceasi parere ca a lui manu;)

[•razyelx]

daca el vrea sa faca binar,lasa-ti-le sa faca binar.
deci Vlad ti-am zis cautarea ta nu poate fi exacta. Deci tu ai vecotrul 2 3 5 7 11 13 17 19.... Iar daca ai a=2 b = 19. Cate numere prime ai? In cazul asta rezolvarea ta va tiparii 8. La a = 4 si b = 19 va tiparii 7, adik corect. Dar daca ai a=2 si b=18 programul tau va afisa 8, corect fiind 7. Iar pt a=4, b = 18 programul tau va afisa 6, corect fiind 5.

uite cautarea mea binara:

Cod:

 long bs(long x){  
      long s=1,d = h,m,i;  
      while(s+2<d){  
     m = (s+d)/2;  
     if(x == prime[m]) return m;  
   
     if(x>prime[m])s = m+1;  
     else d = m-1;  
      }  
      i=s;  
      while(x>prime[i] && i<=d)i++;  
      return i;  
}  

prime[] e vectorul tau s[]. Am lasat ca marginea inferioara sa fie mai mica cu 3 decat cea superiaora ca sa pot cauta secvential exact nr care ma intereseaza pentru ca imi sarea. Nu pot explica foarte exact pt ca am rezolvat-o anul trecut.

iar afisarea:

Cod:

  if(a == prime[i] && b != prime[j]){  
             fprintf(out,"%ld \n",j-i);  
           }  
   
   
           if(a != prime[i] && b == prime[j]){  
             fprintf(out,"%ld \n",j-i+1);  
           }  
   
           if(a == prime[i] && b == prime[j]){  
             fprintf(out,"%ld \n",j-i+1);  
           }  
   
           if(a != prime[i] && b != prime[j]){  
             fprintf(out,"%ld \n",j-i);  
           }  

sper ca te-am ajutat. Apropo pe testul initial de pe infoarena iti merge?

[•shnako]

Nu va luati de om daca vrea sa ajute 
Seba iti multumesc ca vrei sa ma ajuti dar pe toate exemplele tale imi dau bine rezultatele...
O sa incerc si metoda fara binara cand ajung acasa dar ar fi dragut sa o corectam si pe cea cu binara pentru ca pe orice exemplu am intalnit pana acum imi da bine ...
Thanks guys 

[•gabor_oliviu1991]

incearca sa cauti binar pe A, respectiv B, iar daka nu il gasesti returneazati pozitia stanga (limita stanga a intervalului in care il cauti). si atunci verifici daca pe pozitia returnata de cautarea binara ai numar prim sau nu. din cate am observat, te-ai cam complicat acolo.

Cod:

binary(int elem_cautat)
{
start = 1;
finish = k;
while(start <= finish)
{
    middle = (start+finish)/2;
    if( elem_cautat == a[middle])
         return middle
    else
        if(elem_cautat < a[middle])
                  finish = middle -1;
        else
                  start = middle+1;
}
return start;
}

si dupa ai cele 4 conditii pe care le-a postat si sebi mai sus.

[•shnako]

Am facut de 100 cu solutia lui jupanubv92
Desi ar fi frumos sa aflu ce era gresit la cautarea binara ....

[•Ionut_info]

de ce nu merge?!? cred ca-i problema fisierului de intrare si de iesire 

[•Florian]

de ce nu merge?!? cred ca-i problema fisierului de intrare si de iesire 

Problema este de fapt a ta. Nu a fisierelor de intrare/iesire. Spune cum faci si ce erori iti da.

[•andrici_cezar]

Cum ati facut voi cu un ciur ? Eu am facut cu o baza de numere prime si am luat 50 pct, iar cu ciuru i-au doar 40. Am un test la care zice ca iese din timp si la celelalte nu am suficienta memori... Ajutatima macr sa o fac pe aia cu baza de numere prime ca acolo doar ies din tim. 

P.S. am trimis de doua ori aceeasi sursa si o data am luat 40 si o data 50... Ar fi trebuit?