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

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
New poster
Posts: 4
Joined: Sun Feb 11, 2007 6:38 pm
Location: Iran
Contact:

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

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)

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;
int b;
int c;

void prime(int a[] )
{
int i,l,j,num;
num = MAX;
l = sqrt(num);
a= a = 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=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 ;
value--;

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

if( value == (c - (c - c)))
{
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 < 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

Re: 10650 - Determinate Prime

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.

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

Re: 10650 - Determinate Prime

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)

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;

void sieve()
{
int i,j,k,l,m;
prime = false;
prime = 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 << " " << primeList << " " << primeList << " " << primeList << 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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 10650(Determinate prime)

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

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

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)

I have tried each of the input sets from this thread, I found nothing wrong in my outputs. But still wa 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;
int primes;
int low;
int high;
int pos;

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

{
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);

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

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

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

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

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

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!