Imprimă pagina - 1097 Difprim

Titlul: 1097 Difprim
Scris de: Andrei Grigorean din Decembrie 13, 2010, 00:42:55

Aici puteti discuta despre problema Difprim (http://infoarena.ro/problema/difprim).

Titlul: Răspuns: 1097 Difprim
Scris de: George Marcus din Decembrie 20, 2010, 17:33:08

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

Titlul: Răspuns: 1097 Difprim
Scris de: Pripoae Teodor Anton din Decembrie 20, 2010, 18:00:15

Cod:

#include <bitset>

bitset < 10000000> ciur;

Titlul: Răspuns: 1097 Difprim
Scris de: Simoiu Robert din Decembrie 20, 2010, 18:00:28

Ai doua variante : fie folosesti un bitset (http://www.cplusplus.com/reference/stl/bitset/), fie faci ciurul optimizat pe biti (http://infoarena.ro/job_detail/153333?action=view-source).

Titlul: Răspuns: 1097 Difprim
Scris de: Andrei Grigorean din Decembrie 22, 2010, 02:04:16

Citat din mesajul lui: George Marcus din Decembrie 20, 2010, 17:33:08

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.

Titlul: Răspuns: 1097 Difprim
Scris de: Adrian Budau din Decembrie 22, 2010, 12:30:39

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.

Titlul: Răspuns: 1097 Difprim
Scris de: Vlad Tarniceru din Decembrie 30, 2010, 14:11:11

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

Titlul: Răspuns: 1097 Difprim
Scris de: Oancea Catalin din Februarie 08, 2011, 11:16:58

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

Titlul: Răspuns: 1097 Difprim
Scris de: Parfene Narcis din Februarie 08, 2011, 11:32:01

Utilizezi operatorul sizeof:

Cod:

#include<iostream>

using namespace std ;

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

Titlul: Răspuns: 1097 Difprim
Scris de: Oancea Catalin din Februarie 08, 2011, 21:14:54

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

Titlul: Răspuns: 1097 Difprim
Scris de: FMI Romila Remus Arthur din Februarie 08, 2011, 22:53:18

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

Titlul: Răspuns: 1097 Difprim
Scris de: Sorin Rita din Martie 17, 2011, 02:00:03

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

Titlul: Răspuns: 1097 Difprim
Scris de: George Marcus din Martie 17, 2011, 12:47:22

Nu trebuie pe biti. Trebuie sa-l optimizezi putin. Vezi Aici (http://infoarena.ro/ciurul-lui-eratostene)

Titlul: Răspuns: 1097 Difprim
Scris de: Bodnariuc Dan Alexandru din Ianuarie 18, 2012, 16:21:21

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 ](*,)

Titlul: Răspuns: 1097 Difprim
Scris de: Andrei Dinu din Mai 09, 2012, 09:42:51

Nu inteleg ce e incorect pe testul 7?

Multumesc!

Titlul: Răspuns: 1097 Difprim
Scris de: Boaca Cosmin din Mai 09, 2012, 12:36:53

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

Titlul: Răspuns: 1097 Difprim
Scris de: Johnny Depp din Aprilie 14, 2013, 17:56:15

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?

Titlul: Răspuns: 1097 Difprim
Scris de: Stefan Eniceicu din Aprilie 14, 2013, 19:16:12

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..

Titlul: Răspuns: 1097 Difprim
Scris de: Johnny Depp din Aprilie 14, 2013, 20:58:43

mersi mult! :ok:. acum am luat 100p :winner1: .O sa fiu mai atent de acum :oops:

Titlul: Răspuns: 1097 Difprim
Scris de: Mercea Otniel din Ianuarie 31, 2015, 20:54:17

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");
}

Titlul: Răspuns: 1097 Difprim
Scris de: one shot din Ianuarie 04, 2016, 21:51:18

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

Titlul: Răspuns: 1097 Difprim
Scris de: one shot din Ianuarie 04, 2016, 21:51:37

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

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Andrei Grigorean din Decembrie 13, 2010, 00:42:55