10650 - Determinate Prime

[Mushfiqur Rahman]

Dear Monish,
Thanks to u. Your I/O really helped me. I mistake just at that point. After removing that from my code, I got AC.

[arakdev]

Finally I got ac for 10650 but it is clear the difficulty for getting ac from 412 AC for 10650.
I put these hints for those who got WA.

1. If x>y then swap them and compute the result for [x,y].
2. In the problem desciption there's an important note. I translate it as :
Suppose we have this sequence of primes by 6 unit diffrence.
251 257 263 269
If we want to consider above sequence as an answer we should be sure that all sequence numbers are in the [x,y]. So for input 252 269 we should print nothing since 251 is not included. Maybe you consider this part of problem :

If three or more consecutive primes ...

and think 257 263 269 are a sequence of 3 uni-distance primes; but since 251 are one the members of 6 diffrence sequence and it is not included so it is not a desired answer.

Finally try this input :

250 268
252 270
255 269
250 269
251 270
251 269
250 270
0 0

output :
251 257 263 269
251 257 263 269
251 257 263 269
251 257 263 269

for 1st , 2nd and 3rd print nothing and 4 next one have answer.

hope it helps.

[zahid19]

I am getting WA on my following code, can anyone give me some suggestion about my mistake?

Code: Select all

// 10650 determinate prime 
#include <stdio.h>
#include <math.h>
#define MAX 32005

int a[32015];
int b[32015];
int c[32015];

void prime(int a[] )
{
	int i,l,j,num;
	num = MAX;
	l = sqrt(num);
	a[0]= a[1] = 1;
	for(i=4 ; i<= num ; i+=2)
		a[i]= 1 ;
	for(i=3 ; i<=l ; i+=2)
	{
		if(a[i]==0)
		{
			for(j= i*2 ; j <= num ; j= i+j)
				a[j]= 1;
		}
	}
}
int main(void)
{
	int i,x,y,value;	
	int loc = 0 ,pos=0,lenB,flag=0,k,point=0;
	prime(a);
	b[0]=2 ;
	loc=1;
	for(i=3 ; i< 32005 ; i+=2)
	{
		if(a[i]==0)
		{
//			printf("%d\n ",i);
			b[loc++]=i ;
		}
	}
	lenB = loc ;
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	while(scanf("%d%d",&x,&y)!=EOF && (x!=0 || y!=0))
	{
		loc = flag = pos = point = 0;
		while(b[loc] < x)   loc++;

		while(b[loc] <= y)
		{
			pos = 0;
			while( (b[loc]-b[loc-1]) == (b[loc+1]-b[loc]) )
			{		
				c[pos++] = b[loc-1];
				c[pos++] = b[loc];

				flag = 1;
				loc++ ;
			}
			value = c[0] ;			
			value--;

			while(a[value]!=0)    value--;

			if( value == (c[0] - (c[1] - c[0])))
			{
				point = 1;
				break;
			}
			
			value = c[pos-1] ;
			while( a[value] != 0 )   value++ ;

			if( value == ((c[pos-1] - c[pos-2]) + c[pos-1]) )
			{
				point = 1;
				break;
			}
			value = 32010 ;

			if( flag == 1)
			{
				c[pos++] = b[loc-1];
				c[pos++] = b[loc];

				flag=0;

				for(k = 0 ; k < pos ; k++)
				{
					if( c[0] < x )
					{
						point = 1 ;
						break;
					}
					else if( c[pos-1] > y)
					{
						point = 1;
						break;
					}
					if( c[k] != c[k-1] )
						printf("%d ",c[k]);
				}
				if(point == 0)
					printf("\n");
				point = 0 ;	
				pos = 0 ;
			}
			pos = 0 ;
			loc++ ;
		}

	}
	return 0;
}

[Obaida]

I don't know what's going on!!!
have all the cases correct! but WA..!

Code: Select all

removed...

Got acc..

[Jehad Uddin]

At last i got ac,after 4 wa and 5 rte,this is so much interesting prob i think.
Thanks to arakdev .

[BUET]

what is the bug in the code.

Code: Select all

#include<iostream>
#include<vector>

using namespace std;

#define M 32009

vector<int> primeList,v;



bool prime[100009];

void sieve()
{
	int i,j,k,l,m;
	prime[0] = false;
	prime[1] = false;

	for(i = 4; i<= M; i += 2)
	{
		prime[i] = false;
	}

	for(i = 3; i <= M; i += 2)
	{
		if(prime[i])
		{
			for(j = i*i; j < M; j += 2*i)
			{
				prime[j] = false;
			}
		}
	}

	//primeList.clear ();
	primeList.push_back (2);

	for (  i = 3; i <= M; i += 2 ) 
	{
		if ( prime [i] ) primeList.push_back (i);
	}

	int size = primeList.size();

	
	


}

int main(void)
{
	memset(prime,true,sizeof(prime));
	int a,b,s,i,j,k,size;
	int diff;
	sieve();
	 
	while ( scanf ("%d %d", &a, &b) ) 
	{
		//cin >> a >> b;
		if(!a && !b)
			break;
		if( a > b)
		{
			s = a;
			a = b;
			b = s;
		}

		//cout << primeList[0] << " " << primeList[1] << " " << primeList[2] << " " << primeList[3] << endl; 

        size = primeList.size();

		for( i = 0; i < size; i++)
		{
			if(primeList[i] >= a)
				break;
		}

		while(primeList[i+2] <= b)
		{
			j = primeList[i];
			k = primeList[i+1];
			s = primeList[i+2];
			diff = k-j;
			if((i == 0 || (primeList[i] - primeList[i-1] != diff))&& (k-j == s - k))
			{
				cout << j;
				cout << " " << k << " " << s;
				i = i+2;
				while(1)
				{
					if((primeList[i+1] - primeList[i] == diff) && (primeList[i+1] <= b))
					{
						cout << " " << primeList[i];
						i++;
					}
					else
					{
						
						cout << endl;
						break;
					}

				}
			}
			else
			{
				
				i++;
			}
			
		}

			  
	}

	return 0;
}

[sohel]

Did you go over the 4 pages of existing discussions?
Don't create a new thread for a problem that already exists. Make your post in an existing one!

[Mukit Chowdhury]

Getting WA !!!! please give me some sample input,for which my code fails ....

Code: Select all

Accepted... :)

I've not found any bug.... so i'm really frustrated !!!

[brianfry713]

Look at the first line of your output for input 563 30838.

[t.tahasin]

I have tried each of the input sets from this thread, I found nothing wrong in my outputs. But still wa
Please help me to find my bug.

Code: Select all

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <string>
#include <list>
#include <vector>
#include <map>

using namespace std;

bool pFlag[32005];
int primes[4000];
int low[4000];
int high[4000];
int pos;

int Determinate(int i, int val, int x);

void CreatePrimeNumbers()
{
	memset(pFlag, true, sizeof(pFlag));
	int lim = 32000;
	int sq = (int)sqrt((double)lim);
	for(int i = 2; i<=sq; i++)
	{
		if(pFlag[i])
		{
			for(int j = 2; i*j<=lim; j++)
				pFlag[i*j] = false;
		}
	}
	pos = 0;
	for(int i = 2; i<=lim; i++) if(pFlag[i]) primes[++pos] = i;
	for(int i = 1; i<=pos; i++)
	{
		if((i+2)<=pos && primes[i+1]-primes[i] == primes[i+2]-primes[i+1])
		{
			i = Determinate(i, primes[i+1]-primes[i], primes[i]);
		}
		else 
		{
			low[i] = high[i] = -1;
			if(primes[i] == 7841 || primes[i] == 7853)
			{
				low[i] = 7829;
				high[i] = 7853;
			}
		}
	}
}

int Determinate(int i, int val, int x)
{
	if(i==pos || primes[i+1]-primes[i] != val) 
	{
		low[i] = x;
		high[i] = primes[i];
		return i;
	}
	low[i] = x;
	high[i] = primes[Determinate(i+1, val, x)];
}

void printOutput(int x, int y)
{
	for(int i = 1; primes[i]<=y; i++)
	{
		if(low[i]>0)
		{
			if(low[i] >=x && high[i] <=y)
			{
				int ll = low[i];
				if(low[i] == 7829) printf("%d",low[i]);
				else
				{
					printf("%d",primes[i]);
					i++;
				}
				while(low[i]==ll)
				{
					printf(" %d",primes[i]); i++;
				}
				i--;
				printf("\n");
			}
		}
	}
}

int main()
{
	//freopen("test.in", "r", stdin);
	//freopen("test.out", "w", stdout);

	CreatePrimeNumbers();
	int x, y;
	while(scanf("%d %d",&x, &y) && (x || y))
	{
		printOutput(x<y ? x:y, x>y ? x:y);
	}
}

[brianfry713]

Doesn't match the sample I/O.

[t.tahasin]

I checked again now. I got everything alright including sample I/O. @brainfry713: Which compiler are you using? I am using Visual Studio.

[brianfry713]

https://ideone.com/iG87a9
I also ran it on a linux machine using g++, and got this on the sample input:
Program received signal SIGSEGV, Segmentation fault.
0x0000000000400bba in Determinate (i=2, val=2, x=3) at 10650.test.3.c:65
65 high = primes[Determinate(i+1, val, x)];

[mrtensai]

my code run successfully in my machine(i'm using codeBlocks IDE), return 0, and with AC(i checked some AC codes) but when i submit it, i get RTE
here is the code :
http://snipt.org/ABJ9

[brianfry713]

Try input:

Code: Select all

31764 31778
0 0

Also don't print a space at the end of a line.