406 - Prime Cuts

[asif_rahman0]

I can't understand the problem 406(Prime Cuts).Can anybody tell me what to do?Plz help me.

[Rocky]

As I Remember The Problem Description Is Very Simple.
The Input Will n & c.You Have To Print c*2 (IF The Prime List is EVEN) or (c*2 -1) (IF The Prime List is ODD) prime from the center odf the list of prime number of (1 to n).
For Example If The n=21 & c = 2.
Then The Prime From 1 to 21 Are : 1,2,3,5,7,11,13,17,19 Total 9 Prime Number So The List Is ODD.(1 Is Prime For This Problem)
So You Need to Print (2*c-1 = 3), 3 Prime Number From The Center Of The List.
So The Output Will 5,7,11.

I THINK IT WILL CLEAR TO YOU NOW.

GOOD LUCK
ROCKY

[asif_rahman0]

Hello thank u for ur help.Yes I've now implement my code and got AC.Thanks again for ur help.

[sfwejfish]

#include<iostream>
using namespace std;
int main(){
int prime[170]={0,1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997};
int in1,in2,x,min,max;
while(cin){
cin>>in1>>in2;
cout<<in1<<" "<<in2<<":";
for(x=1;;x++)
if(prime[x]>in1)
break;
x-=1;
min=(x/2)-in2+1;
if(x%2==1)
min+=1;
if(min<1)
min=1;
max=x+1-min;
for(x=min;x<=max;x++)
cout<<" "<<prime[x];
cout<<endl<<endl;
}
return 0;
}

I have tested all sample inputs,and the outputs are all cerrect.
Why WA?

[chunyi81]

Your code fails for the following input:

Input:

Code: Select all

21 2
18 2
523 40
18 18
100 7
1000 25
1000 12
523 40
12 10
21 3
99 25
100 100
723 12

Correct output:

Code: Select all

21 2 : 5 7 11

18 2 : 3 5 7 11

523 40 : 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461

18 18 : 1 2 3 5 7 11 13 17

100 7 : 13 17 19 23 29 31 37 41 43 47 53 59 61 67

1000 25 : 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593

1000 12 : 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499

523 40 : 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461

12 10 : 1 2 3 5 7 11

21 3 : 3 5 7 11 13

99 25 : 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

100 100 : 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

723 12 : 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379

Your program output:

Code: Select all

21 2 : 5 7 11

18 2 : 3 5 7 11

523 40 : 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461

18 18 : 1 2 3 5 7 11 13 17

100 7 : 13 17 19 23 29 31 37 41 43 47 53 59 61 67

1000 25 : 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601

1000 12 : 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509
523 40 : 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461

12 10 : 1 2 3 5 7 11

21 3 : 3 5 7 11 13

99 25 : 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

100 100 : 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

723 12 : 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379

723 12 : 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379

And to read input for this problem, try while(cin >> in1 >> in2) instead of while(cin) so that you do not have a duplicate output for input: 723 12 as shown above.

[sfwejfish]

Thank for your help.
But I test
while(cin>>in1>>in2)
and
while(cin>>in1){
cin>>in2;
after seeing your post.
And still get 2 WA= ="
Maybe I have to write a new cade?

[Wei-Ming Chen]

I tried many inputs, they are all right, but I still got WA
Can someone help me?



#include <stdio.h>
#include <math.h>
int main()
{
int a[200],b,c,d,e,f;
a[1]=1;
a[2]=2;
a[3]=3;
c=3;
for(b=5;b<=1000;b++)
{
d=(int)(sqrt(b));
for(e=2;e<=d;e++)
{
if(b%e==0)
{
goto cc;
}
}
c++;
a[c]=b;
cc:;
}
while(scanf("%d %d",&b,&c)==2)
{
printf("%d %d:",b,c);
for(d=1;d<=200;d++)
{
if(b<a[d])
{
d--;
break;
}
}
if(d%2==0)
{
e=d/2-c+1;
f=d/2+c;
if(e<=0)
{
e=1;
f=d;
}
}
else
{
e=(d+1)/2-c+1;
f=(d+1)/2+c-1;
if(e<=0)
{
e=1;
f=d;
}
}
for(d=e;d<=f;d++)
{
printf(" %d",a[d]);
}
printf("\n\n");
}
return 0;
}

[hinyinlam]

I don't know why I always get WA, both of them have correct output when using the test case given by the problem set. Thanks for any help!:)
And the output formate is unclear, for example for the input 18 18
Should I output:

Code: Select all

18 18: 1 2 3 5 7 11 13 17
(blank line)
// that means should I use cout << answer << endl << endl;

OR

Code: Select all

18 18: 1 2 3 5 7 11 13 17 // that means should I use cout << answer << endl;?

??????

Code one: Store all things first then calculate it

Code: Select all

#include <iostream>
#define no_prime 10000
#define no_input 500
using namespace std;
int main(){
	int temp[no_prime];
	int store_n[no_input];
	int store_c[no_input];
	int count=0;
	int n;
	int c;
	while(cin >> n >>c){
		store_n[count]=n;
		store_c[count]=c;
		count++;
	}
	for(int k=0;k<count;k++){
		int temp_count=0;
		int isPrime =1;
		cout << store_n[k] << " " << store_c[k] << ": ";
	//	cout <<": ";

		for(int i=1;i<=store_n[k];i++,isPrime=1){
			for(int j=2;j<i;j++){
				if((i%j)==0&&i!=j){
					isPrime=0;
					break;
				}
			}
			if(isPrime==1){
				//cout << i << " ";
				temp[temp_count]=i;
				temp_count++;
			}
		}
		if(store_c[k]<temp_count){
			if(temp_count%2==0){//even range= temp_count/2+1 -c to  temp_count/2+1 +c
				temp_count=temp_count/2;
				for(int i=temp_count-store_c[k];i<temp_count+store_c[k];i++){
					cout<< temp[i] << " ";
				}
				cout << endl;
			}else{//odd range =temp_count/2
				temp_count=temp_count/2;
				for(int i=temp_count-store_c[k]+1;i<temp_count+store_c[k];i++){
					cout << temp[i]<< " ";
				}
				cout << endl;
			}
		}else{//print out all if c >= temp_count
				for(int i=0;i<temp_count;i++){
					cout<< temp[i] << " ";
				}
				cout << endl;
		}
		cout << endl;
	}
	return 0;
}

Code two: Calculate when there's input

Code: Select all

#include <iostream>
#define no_prime 1000
using namespace std;
int main(){
	int temp[no_prime];
	int n;
	int c;
	while(cin){
		cin >> n >> c;
		int temp_count=0;
		int isPrime =1;
		cout << n << " " << c << " : ";
		//cout << "\b: " ;
		for(int i=1;i<=n;i++,isPrime=1){
			for(int j=2;j<i;j++){
				if((i%j)==0&&i!=j){
					isPrime=0;
					break;
				}
			}
			if(isPrime==1){
				//cout << i << " ";
				temp[temp_count]=i;
				temp_count++;
			}
		}
		if(c<temp_count){
			if(temp_count%2==0){//even range= temp_count/2+1 -c to  temp_count/2+1 +c
				temp_count=temp_count/2;
				for(int i=temp_count-c;i<temp_count+c;i++){
					cout<< temp[i] << " ";
				}
				cout << endl;
			}else{//odd range =temp_count/2
				temp_count=temp_count/2;
				for(int i=temp_count-c+1;i<temp_count+c;i++){
					cout << temp[i]<< " ";
				}
				cout << endl;
			}
		}else{//print out all if c >= temp_count
				for(int i=0;i<temp_count;i++){
					cout<< temp[i] << " ";
				}
				cout << endl;
		}
	}
	return 0;
}

[Jan]

Your code is almost ok. Finally I got your error...

Input:

Code: Select all

997 1

Output:

Code: Select all

433

Hope it helps.

[Jan]

You need primes less than 1000 only. Why you are generating primes less than 1000010? So you are getting TLE.

[Jan]

Your code has a lot of errors.

Input:

Code: Select all

900 79

Output:

Code: Select all

900 79: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887

(The output is in one line)

Hope it works.

[Jan]

I used the following method...

Code: Select all

18 18: 1 2 3 5 7 11 13 17 
(blank line) 
// that means should I use cout << answer << endl << endl;  Yes is the answer

Change the following lines..

Code: Select all

cout << n << " " << c << " : "; //Your code
cout << n << " " << c << ":";  //Should be

Code: Select all

cout<< temp[i] << " "; //your code
cout<<  " " <<temp[i] ; //should be

And add a new line after each test case.

Hope it works.

[kolpobilashi]

i got TLE 4 dis code,and cant get the reason, anybody tell me y n wats de solution.....




[/code]#include<stdio.h>

int isPrime(int num)
{
int k,j;
if(num==1||num==2) return num;
if(num%2==0) return 0;
j=sqrt(num);
for(k=3;k<=j;k+=2)
if(num%k==0)
return 0;
return num;
}


int main()
{
int input1,input2,i;
int ch1[1003],ch2[170];
for(i=0;i<=1003;i++)
ch1[i]=isPrime(i);
while(scanf("%d %d",&input1,&input2)==2)
{
int n,L,m=0,prime=0;
for(n=0;n<=input1;n++)
if(ch1[n]!=0)
{
ch2[m++]=ch1[n];
prime++;
}
printf("%d %d: ",input1,input2);
if(input2<prime)
{
if(prime%2==0)
{
prime=prime/2;

for(L=(prime-input2);L<(prime+input2);L++)
printf("%d ",ch2[L]);
}
else
{
prime=prime/2;
for(L=(prime+1-input2);L<(prime+input2);L++)
printf("%d ",ch2[L]);
}
}
else
for(L=0;L<prime;L++)
printf("%d ",ch2[L]);

printf("\n\n");
}
return 0;
} [quote][/quote]

[mamun]

i got TLE 4 dis code,and cant get the reason, anybody tell me y n wats de solution.....

Nice English!!!

Code: Select all

for(i=0;i<=1003;i++) 
ch1[i]=isPrime(i);

Your array size is 1003. So what should be the last index? Is it OK to be i=1003 and trying to index ch1?

[kolpobilashi]

well, i fixed that problem but now i got WA!!!! would plz check out if there is any mistake in my code or in my logic?! i got confused n tired.....