10650 - Determinate Prime

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Mushfiqur Rahman
Learning poster
Posts: 56
Joined: Tue Jun 13, 2006 5:18 pm
Location: (CSE, SUST) Sylhet, Bangladesh
Contact:

Thanks to Monish

Post by Mushfiqur Rahman » Mon Oct 09, 2006 7:42 pm

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

User avatar
arakdev
New poster
Posts: 4
Joined: Sun Feb 11, 2007 6:38 pm
Location: Iran
Contact:

Before the other , read me first ... 10650 help

Post by arakdev » Fri Apr 06, 2007 10:47 pm

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
New poster
Posts: 1
Joined: Sun Feb 10, 2008 5:11 pm
Location: Dhaka

10650 determinate prime (WA)

Post by zahid19 » Sun Feb 10, 2008 5:33 pm

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
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10650 - Determinate Prime

Post by Obaida » Sat Apr 18, 2009 8:00 am

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

Code: Select all

removed...
Got acc.. :)
Last edited by Obaida on Sun Jul 12, 2009 8:10 pm, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 10650 - Determinate Prime

Post by Jehad Uddin » Sun Jul 12, 2009 7:24 pm

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

BUET
New poster
Posts: 22
Joined: Sun Jun 13, 2010 8:38 am

10650(Determinate prime)

Post by BUET » Sun Jan 09, 2011 11:26 am

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

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 10650(Determinate prime)

Post by sohel » Mon Jan 10, 2011 11:19 am

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
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 10650 - Determinate Prime

Post by Mukit Chowdhury » Tue Oct 09, 2012 3:17 pm

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

Code: Select all

Accepted... :)
:cry:
I've not found any bug.... so i'm really frustrated !!! :(
Last edited by Mukit Chowdhury on Thu Nov 08, 2012 10:43 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10650 - Determinate Prime

Post by brianfry713 » Tue Oct 09, 2012 10:43 pm

Look at the first line of your output for input 563 30838.
Check input and AC output for thousands of problems on uDebug!

t.tahasin
New poster
Posts: 38
Joined: Tue May 28, 2013 11:21 pm

Re: 10650 - Determinate Prime (WA)

Post by t.tahasin » Tue May 28, 2013 11:29 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10650 - Determinate Prime

Post by brianfry713 » Wed May 29, 2013 12:45 am

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

t.tahasin
New poster
Posts: 38
Joined: Tue May 28, 2013 11:21 pm

Re: 10650 - Determinate Prime

Post by t.tahasin » Wed May 29, 2013 1:01 am

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10650 - Determinate Prime

Post by brianfry713 » Wed May 29, 2013 11:58 pm

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)];
Check input and AC output for thousands of problems on uDebug!

mrtensai
New poster
Posts: 1
Joined: Wed Jul 03, 2013 8:57 pm

Re: 10650 - Determinate Prime

Post by mrtensai » Wed Jul 03, 2013 9:06 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10650 - Determinate Prime

Post by brianfry713 » Thu Jul 04, 2013 1:40 am

Try input:

Code: Select all

31764 31778
0 0
Also don't print a space at the end of a line.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 106 (10600-10699)”