10650 - Determinate Prime

[emo]

why WA

Code: Select all

#include<iostream>
#include<map>
#include<vector>
#include<set>
using namespace std;
bool prime[32010];
int primes[32000];
void sieve()
{
	for(int i=0;i<32000;i++)
		prime[i]=true;
	prime[0]=false;prime[1]=false;
	for(int i=2;i*i<=32000;i++)
		if(prime[i])
		{
			for(int j=i*i;j<=32000;j+=i)
				prime[j]=false;
		}
}
int main()
{
	sieve();
	int a,b,x,y;
	while(cin>>x>>y)
	{
		if(x==0&&y==0)
			break;
		if(x<y){
			a=x;b=y;
		}
		else
		{
			a=y;b=x;
		}
		int tmp,k=0;
		vector<int>v;
		for(int i=a;i<=b;i++)
		{
			if(prime[i])
			{
				primes[k]=i;
				k++;
			}
		}
		primes[k+1]=0;
		bool flag=false;
		for(int i=0;i<=k;i++)
		{
			if(v.size()<2)
				v.push_back(primes[i]);
			else
			{
				if(primes[i]-primes[i-1]==primes[i-1]-primes[i-2])
					v.push_back(primes[i]);
				else
				{
					if(v.size()==2)
					{
						v.clear();
						i-=2;
					}
					else
					{
						cout<<v[0];
						for(int j=1;j<v.size();j++)
							cout<<" "<<v[j];
						cout<<endl;
						i-=2;
					}
					v.clear();

				}
			}
		}
	}
	return 0;
}

[brianfry713]

Input:

Code: Select all

23335 8226
0 0

AC output:

Code: Select all

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
19937 19949 19961
20101 20107 20113
20117 20123 20129
20149 20161 20173
20183 20201 20219
20341 20347 20353
20509 20521 20533
20719 20731 20743
21157 21163 21169
21649 21661 21673
21893 21911 21929
21991 21997 22003
22039 22051 22063
22067 22073 22079
22247 22259 22271
22441 22447 22453

[emo]

Input:

Code: Select all

23335 8226
0 0

AC output:

Code: Select all

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
19937 19949 19961
20101 20107 20113
20117 20123 20129
20149 20161 20173
20183 20201 20219
20341 20347 20353
20509 20521 20533
20719 20731 20743
21157 21163 21169
21649 21661 21673
21893 21911 21929
21991 21997 22003
22039 22051 22063
22067 22073 22079
22247 22259 22271
22441 22447 22453

why is 23321 23327 23333 not one of the output sequences?

[brianfry713]

NB: No subset of a series is allowed. For example, a series of five uni-distant primes having even four of them in the interval is not allowed, all the five primes should be in the interval.

For input:

Code: Select all

23339 23321
0 0

AC output:

Code: Select all

23321 23327 23333 23339

[musfiqur.cse]

Why i'm getting WA.. Please help .. I triend all input and output..

Code: Select all

Thank you Very much ! got accepted

[lighted]

Try to read posts in this thread first.

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.

Don't forget to remove your code after getting accepted.

[mahmoud.saied]

Code: Select all

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fore(i,n) for(int i = 0; i< n ; i++ )
#define lop(i,n) for(int i = 1 ; i<=n ; i++ )
#define ops(i,n) for(int  i = n-1 ; i>=0 ; i-- )
#define PI  3.141592653589793
#define mod  1000000007
#define inf 1000000000
using namespace std;
int n = 33000;
bool  prime[40000];
vector <int>  p;
int size ;
vector <vector < int > > ax(200);
void solve(){
    fill_n(prime,40000,true);
    prime[0] = false;
    prime[1] = false;
    for(int i = 2 ; i * i <=n ; i++){
        if(prime[i]){
            for(int j = i + i ;j <=n ; j += i){
                prime[j] = false;
            }
        }
    }
    fore(i , n+1){
        if(prime[i])p.pb(i);
    }
}
void fuck()
{
    int c = -1;
    for(int i = 0 ; i < size - 2 ; i++){
        int alt  = abs(p[i+1]-p[i]) ;
        int alto = abs(p[i+2]-p[i+1]);
        if(alt == alto){
            vector <int> ans;
            ans.pb(p[i]);
            ans.pb(p[i+1]);
            ans.pb(p[i+2]);
            c++;
            if(i+3 < size && p[i+3] - p[i+2] == alto){
                ans.pb(p[i+3]);
                ax[c] = ans;
                i+=3;
            }else {ax[c] = ans;i+=2;}
            ans.clear();
        }
    }
}
int main()
{
    solve();
    int x , y,a,b ;
    size = p.size();
    fuck();
    while(scanf("%d %d",&a,&b) == 2){
        if(!a && !b)break;
        x = min(a,b);y = max(a,b);
        if(y > 32000)y=32000;
        fore(i , 164){
            if(ax[i][0]>=x && ax[i][ax[i].size()-1] <= y){
                fore(j , ax[i].size()){
                    if(j)cout <<" "<< ax[i][j];
                    else cout << ax[i][j] ;
                }
                cout <<endl;
            }
        }
    }
    return 0;
}

[brianfry713]

Input:

Code: Select all

0 32000
0 0

AC output:

Code: Select all

3 5 7
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
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
19937 19949 19961
20101 20107 20113
20117 20123 20129
20149 20161 20173
20183 20201 20219
20341 20347 20353
20509 20521 20533
20719 20731 20743
21157 21163 21169
21649 21661 21673
21893 21911 21929
21991 21997 22003
22039 22051 22063
22067 22073 22079
22247 22259 22271
22441 22447 22453
23321 23327 23333 23339
23761 23767 23773
23789 23801 23813
23887 23893 23899
24071 24077 24083
24091 24097 24103
24407 24413 24419
24671 24677 24683
25373 25391 25409
25457 25463 25469
25609 25621 25633
25667 25673 25679
26029 26041 26053
26171 26177 26183 26189
26387 26393 26399
26687 26693 26699
26717 26723 26729
26981 26987 26993
27061 27067 27073
27767 27773 27779
28057 28069 28081
28591 28597 28603
28921 28927 28933
29167 29173 29179
29251 29269 29287
29327 29333 29339
29587 29599 29611
29867 29873 29879
30047 30059 30071
30091 30097 30103 30109
30307 30313 30319
30431 30449 30467
30631 30637 30643 30649
30971 30977 30983
31039 31051 31063
31321 31327 31333