1097 Difprim

[•wefgef]

Aici puteti discuta despre problema Difprim.

[•PlayLikeNeverB4]

Cum se aloca memoria pentru 100p? Daca folosesc un vector de 10 000 000 elemente iau decat 60 din cauza memoriei.

[•toni2007]

Cod:

#include <bitset>

bitset < 10000000> ciur;

[•SpiderMan]

Ai doua variante : fie folosesti un bitset, fie faci ciurul optimizat pe biti.

[•wefgef]

Cum se aloca memoria pentru 100p? Daca folosesc un vector de 10 000 000 elemente iau decat 60 din cauza memoriei.

Poti declara 10 milioane de bool, nu de int.

[•freak93]

Bool nu prea e folositor ca tip de date, consuma 1 byte pentru a mentine 2 valori(true and false). Desi in conditiile de fata intra in memorie la unele probleme s-ar putea sa nu intre.

[•vladtarniceru]

am nevoie de putin ajutor, am 2 surse aproape identice, una de 100 si alta de 60 si chiar nu vad care e diferenta
sursa de 100:

Cod:

# include <fstream>
  using namespace std;
    int A, B, st, dr, p1, p2, sol;
	char a[(10000000 >> 3) + 100000];
    int main (){
		ifstream f ("difprim.in");
		ofstream g ("difprim.out");
		f >> A >> B;
		int i = 4;
		for (i = 4; i <= 10000000; i += 2)
			a[i >> 3] |= (1 << (i & 7) );
		i = 1;
		while (i <= 400000){
			do{ 
				i += 2;
			}while (     ( a[i >> 3] & (1 << (i & 7) ) )      );
			for (int j = i + i; j <= 10000000; j += i) 
				a[j >> 3] |= (1 << (j & 7) );
		}
		//for (i = 1; i <= 30; ++i) 
		//	if (    !( a[i >> 3] & (1 << (i & 7) ) )      )
		//		g << i << ' ';
		for (i = A + 1; i < B; ++i){
			if (  !(   a[i >> 3] & (1 << (i & 7) )   )  ){
				st = dr;
				dr = i;
				if (sol < dr - st && st){
					sol = dr - st;
					p1 = st;
					p2 = dr;
				}
			}
		}
		if (!sol) g << "-1\n";
		else
			g << p1 << ' ' << p2 << '\n';
		g.close ();
		return 0;
	}
	

si cea de 60:

Cod:

# include <fstream>
  using namespace std;
    std :: ifstream f ("difprim.in");
	std :: ofstream g ("difprim.out");
	char a[(10000000 >> 3) + 10000];
	int A, B;
	void ciur (){
		for (int i = 4; i <= 10000000; i += 2)
			a[i >> 3] |= (1 << (i & 7) );
		int i = 1;
		while (i <= 100000){
			do {
				i += 2;
			} while (a[i >> 3] & (1 << (i & 7) ));
			for (int j = i + i, val = (i << 1); j <= 10000000; j += i) a[j >> 3] |= (1 << (j & 7) );
		}
	}
	int af1, af2, MAX = 0;
	int main (){
		f >> A >> B;
		ciur ();
		int ac, an;
		for (int i = A + 1; i < B; ++i){
			if ( !(a[i >> 3] & (1 << (i & 7) ) ) ){
				an = ac, ac = i;
	    		if (MAX < ac - an && an){
				    MAX = ac - an;
					af1 = an;
					af2 = ac;
				}
			}
		}
		if (!MAX) g << "-1\n";
		else
			g << af1 << ' ' << af2 << '\n';
		return 0;
	}

as fi recunoscator celui care mi-ar zice ce e gresit in cea de-a doua
multumesc  

[•Oancea.Catalin]

cum stiu cata memorie ocupa un vector? de exemplu int a[100] ... are legatura daca e declarat int sau long?

[•nparfene2004]

Utilizezi operatorul sizeof:

Cod:

#include<iostream>

using namespace std ;

int main()
{
	int a[10000] ;
	
	cout << sizeof(a) ;
	
	return 0 ;
}

[•Oancea.Catalin]

si sizeof(a)... e dat in  kbytes ? 

[•R.A.R]

Nu : Returns the total size, in bytes, of the input variable.

[•soriyn]

i-a intrat cuiva in timp,pe toate testele, fara ciur pe biti ?

[•PlayLikeNeverB4]

Nu trebuie pe biti. Trebuie sa-l optimizezi putin. Vezi Aici

[•dutzul]

pff nu mai stiu ce sa optimizez pe el imi ia TLE pe ultimu test.. am facut ciur cu niste optimizari(j=i*i),i*i<=b; mda si cam asta e 

[•informatician28]

Nu inteleg ce e incorect pe testul 7?

Multumesc!

[•darkseeker]

Ai afisat -1 in cazul in care nu ai solutie ?

[•Johny_Depp22]

ce e cu testul 6? Iau incorect pe el si nu stiu de ce. am luat in considerare si cazul in care nu exista solutie si tot 90p iau. vreo idee?

[•Steve]

Cod:

if (i-prec>dif && prec >= A)

..tu gasesti doua prime, din care unu poate sa fie mai mic decat A in forul ala si zici la sfarsit ca daca perechea pe care ai gasit-o e mai mica decat a n-ai solutie, ceea ce e gresit. Ex, ai a = 11, b = 13...o sa iti dea -1, chiar daca ai solutie..

[•Johny_Depp22]

mersi mult!  . acum am luat 100p   .O sa fiu mai atent de acum  

[•otniel]

ce este gresit la sursa asta ca da incorect pe testu 1

#include<iostream>
using namespace std;
#include<stdio.h>
#include<math.h>
int i,j,a,b,maxim,u,q,w,t,nr;
bool c[10000000];
FILE *f,*g;
int main()
{
     f=fopen("difprim.in","r");
    g=fopen("difprim.out","w");
     fscanf(f,"%d %d",&a,&b);
  for (i = 3; i <= sqrt(b); i += 2) {
    if (c == 0) {
      for (j = i+i+i; j <= b; j += i << 1) {
        c[j] = 1;
      }
    }
  }
    if(a%2==0)
        a++;
    for(i=a;i<=b;i=i+2)
        if(!c)
        {u=i;
    break;}
      for(i=u+2;i<=b;i=i+2)
        if(c==0)
      {
          if(i-u>maxim)
          {
              maxim=i-u;
              q=u;
              w=i;
          }
          u=i;
      }
      if(q!=w&&q!=0&&w!=0)
      fprintf(g,"%d %d",q,w);
      else
        fprintf(g,"-1");
}

[•RG1999]

Algoritmul tau nu l ia in considerare pe 2. Aceeasi greseala am avut o si eu

[•RG1999]

Algoritmul tau nu l ia in considerare pe 2. Aceeasi greseala am avut o si eu