10650 - Determinate Prime

erdos · Post by **erdos** » Tue May 04, 2004 10:19 pm

Hi,

I was solving this problem and I don't understand the sample output for the sample input.
When input is: "1 100" the sample output is:
3 5 7
47 53 59

My program gives:
3 5 7
31 37 43
47 53 59
61 67 73 79

and I don't see how it may be wrong. Can somebody explain me why
31 37 43
61 67 73 79

aren't solutions ? They seem right according to the problem description.

Kuba12 · Post by **Kuba12** » Tue May 04, 2004 11:06 pm

I gave up solving this problem as I don't know how to sort the output values (should I output "x x+2 x+4" or "x x+4 x+8" first?
moreover, I am uncertain whether I should output a series that is a subsequence of a sequence, whose biggest element is greater than 32000.
confused,
Kuba

mavy · Post by **mavy** » Tue May 04, 2004 11:08 pm

Hi,

31 37 43

you sequence must be consecutive, you missed 41 on this one.

If three or more consecutive primes...

I found 156 sequences from 1 to 32000, is this correct ?

Larry · Post by **Larry** » Tue May 04, 2004 11:16 pm

This problem is trivial, but I had to resubmit once because of this:

The input is consist of several test cases. Each test case consists of two non negative integers x and y. None of the input will be grater than 32000. Input will be terminated with two zeroes.

Emphasis on "nonnegative"

I had read input with:

Code: Select all

while ( 2 == scanf("%d %d\n", &x, &y ) && x && y )

and it WA's, because it contains queries like:

Code: Select all

0 32000

with 0 in one of them.

Another (possible) mistake is that x doesn't have to be less than y. I don't know if it's in the input, but I assume it didn't..

Adrian Kuegel · Post by **Adrian Kuegel** » Tue May 04, 2004 11:19 pm

You have to read the problem description very careful. As mavy said, only consecutive primes are called determinate. But 31 37 43 are not consecutive, because 41 is missing.
And please read the NB part: you should only output a maximum sequence of determinate primes, no subset of it.
So try these test cases:
251 263
251 269

For first test case you should output nothing, for second test case you should print:
251 257 263 269
As you can see, the given limits of the interval are included, so the interval given here ranges from 251 to 269 with 251 and 269 included. I think this is the usual way how "between" is used, but the problem description should have contained some word that the endpoints are included to the interval.

sunhong · Post by **sunhong** » Wed May 05, 2004 7:58 am

I got several WA on this problem

But I think I take every cases to account,please help me!
[cpp]#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <vector>
using namespace std;

const int maxn=33500;
vector<int> temp;
bool prime[maxn];
int A,B,N,p[maxn];

int find(int sign,int s)
{
int low,mid,high;
low=0; high=N-1;
while (low<=high){
mid=(low+high)/2;
if (s==p[mid]) return mid;
if (p[mid]<s) low=mid+1;
else high=mid-1;
}
if (sign==1) return low;
else return high;
}
void swap(int &a,int &b)
{
int t;
t=a; a=b; b=t;
}
int main()
{
int i,j,k,step,L,R;
for (i=1;i<maxn;i++) prime=true;
N=0;
for (i=2;i<maxn;i++){
if (!prime) continue;
p[N++]=i;
j=2*i;
while (j<maxn){
prime[j]=false;
j+=i;
}
}
//printf("N=%d\n",N);
while (1){
scanf("%d%d",&A,&B);
if (A==0 && B==0) break;
if (A>B) swap(A,B);
L=find(1,A); R=find(2,B);
//printf("p[%d]=%d p[%d]=%d\n",L,p[L],R,p[R]);
if (R-L<=1) continue;
i=L;
while (i<=R-2){
j=i+1; step=p[j]-p;
temp.clear();
temp.push_back(p); temp.push_back(p[j]);
while (j<=R){
if (p[j+1]<=B && p[j+1]-p[j]==step) temp.push_back(p[++j]);
else break;
}
int size=temp.size();
if (size>=3){
if (i>1 && p[i-1]<A && p-p[i-1]==step){
i++; continue;
}
if (p[j+1]>B && p[j+1]-p[j]==step){
i++; continue;
}
for (k=0;k<size;k++)
printf("%d%c",temp[k],(k==size-1) ? '\n':' ');
i=j+1;
}
else i++;
}
}
return 0;
}[/cpp]

HidWalker · Post by **HidWalker** » Wed May 05, 2004 9:12 am

Sorry, I know what you mean,
Thx.

Larry · Post by **Larry** » Wed May 05, 2004 9:47 am

A prime number can appear in more than one sequence - as the start of one and the end of the other.

PS: Please remove your list.. =)

sohel · Post by **sohel** » Wed May 05, 2004 12:38 pm

If I am not mistaken, the problem description does not inform us about the order of the output....

.. but for the sake of brevity I assumed the obvious... though WA.

Can somebody verify these input / output.

[c]
input

25 97
100 1000
256 19871
33 133
15 29
0 1
0 10
0 0
[/c]

[c]
output

47 53 59
151 157 163
167 173 179
199 211 223
251 257 263 269
367 373 379
557 563 569
587 593 599
601 607 613
647 653 659
727 733 739
941 947 953
971 977 983
257 263 269
367 373 379
557 563 569
587 593 599
601 607 613
647 653 659
727 733 739
941 947 953
971 977 983
1097 1103 1109
1117 1123 1129
1181 1187 1193
1217 1223 1229
1361 1367 1373
1499 1511 1523
1741 1747 1753 1759
1901 1907 1913
2281 2287 2293
2411 2417 2423
2671 2677 2683
2897 2903 2909
2957 2963 2969
3301 3307 3313 3319
3631 3637 3643
3727 3733 3739
4007 4013 4019
4397 4409 4421
4451 4457 4463
4591 4597 4603
4651 4657 4663
4679 4691 4703
4987 4993 4999
5101 5107 5113 5119
5297 5303 5309
5381 5387 5393 5399
5557 5563 5569
5801 5807 5813
6067 6073 6079
6257 6263 6269
6311 6317 6323 6329
6361 6367 6373 6379
6857 6863 6869
6971 6977 6983
7517 7523 7529
7577 7583 7589
7817 7823 7829
7829 7841 7853
8111 8117 8123
8707 8713 8719
8741 8747 8753
9391 9397 9403
9467 9473 9479
9859 9871 9883
10247 10253 10259
10601 10607 10613
10651 10657 10663
10847 10853 10859
11287 11299 11311
11399 11411 11423
11491 11497 11503
11719 11731 11743
11801 11807 11813
11897 11903 11909
11927 11933 11939
12491 12497 12503
12541 12547 12553
12577 12583 12589
12641 12647 12653 12659
12829 12841 12853
12967 12973 12979
13037 13043 13049
13171 13177 13183
13451 13457 13463 13469
14537 14543 14549
14741 14747 14753 14759
15149 15161 15173
15187 15193 15199
15307 15313 15319
15461 15467 15473
15761 15767 15773
15791 15797 15803 15809
15901 15907 15913 15919
16091 16097 16103
16217 16223 16229
16421 16427 16433
16481 16487 16493
16561 16567 16573
16607 16619 16631
16763 16787 16811
16931 16937 16943
16981 16987 16993
17041 17047 17053
17321 17327 17333
17419 17431 17443
17471 17477 17483 17489
17839 17851 17863
18211 18217 18223 18229
18329 18341 18353
18427 18433 18439
18719 18731 18743
19457 19463 19469
19471 19477 19483 19489
19571 19577 19583
19597 19603 19609
19727 19739 19751
47 53 59
3 5 7
[/c]

And I got 162 different determinate sequence for 0 32000.
Is this correct?

UFP2161 · Post by **UFP2161** » Wed May 05, 2004 1:16 pm

Look at your own output for 100 1000 and 256 19871. Then think about the NB note in the problem.

LPH · Post by **LPH** » Wed May 05, 2004 3:57 pm

Larry wrote:Another (possible) mistake is that x doesn't have to be less than y. I don't know if it's in the input, but I assume it didn't..

Well, i think it does.

My program was WA before this correction, and is AC after.

Aleksandrs Saveljevs · Wed May 05, 2004 10:22 pm

mavy wrote:I found 156 sequences from 1 to 32000, is this correct ?

No.

sohel wrote:And I got 162 different determinate sequence for 0 32000. Is this correct?

Yes.

dll · Post by **dll** » Thu May 06, 2004 8:47 am

I got WA so many times , I can't find my bug
[cpp]

[/cpp]

sumankar · Post by **sumankar** » Thu May 06, 2004 9:16 am

If np is the number of primes dont you think in C:

Code: Select all

[c]
for(ii=i+1; ii<=np && prime[ii]<=y; ii++)
 if(j!=prime[ii] ...
[/c]

might land you in trouble ?

hth
Suman

dll · Post by **dll** » Thu May 06, 2004 9:59 am

" If np is the number of primes dont you think in C: "
sorry, I don't understand your english.
thank you all the same.

OJ Board

10650 - Determinate Prime

10650 - Determinate Prime

not sure

Hi: