OJ Board

The Online Judge board
https://onlinejudge.org/board/

406 - Prime Cuts

https://onlinejudge.org/board/viewtopic.php?t=8141

Page 4 of 13

406 - Prime Cuts

Posted: Tue May 17, 2005 6:44 pm
by asif_rahman0
I can't understand the problem 406(Prime Cuts).Can anybody tell me what to do?Plz help me.

Reply On 406

Posted: Thu May 19, 2005 8:07 am
by 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

Thaks for help

Posted: Sat May 21, 2005 7:09 pm
by asif_rahman0
Hello thank u for ur help.Yes I've now implement my code and got AC.Thanks again for ur help.

406...WA??WHY??All sample inputs are cerrect...

Posted: Wed Aug 10, 2005 7:21 am
by 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?

Posted: Sun Aug 14, 2005 2:57 pm
by 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.

Posted: Mon Aug 15, 2005 1:27 am
by 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?

406 WA.....

Posted: Mon Nov 14, 2005 2:35 pm
by 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;
}

Again, It's 406 prime cut Need Help! WA

Posted: Sun Nov 27, 2005 4:45 pm
by 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;
}
:)

Posted: Fri Dec 23, 2005 9:26 pm
by 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.

Posted: Fri Dec 23, 2005 9:29 pm
by Jan
You need primes less than 1000 only. Why you are generating primes less than 1000010? So you are getting TLE.

Posted: Fri Dec 23, 2005 9:43 pm
by 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.

Posted: Fri Dec 23, 2005 9:58 pm
by 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.

406 got TLE,help me!!

Posted: Tue Jan 17, 2006 5:07 pm
by 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;
} :roll:[quote][/quote]

Re: 406 got TLE,help me!!

Posted: Tue Jan 17, 2006 5:25 pm
by mamun
kolpobilashi wrote:i got TLE 4 dis code,and cant get the reason, anybody tell me y n wats de solution..... :(
Nice English!!! :o

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?

hmmmm....now wat?!

Posted: Tue Jan 17, 2006 9:45 pm
by 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..... :(
All times are UTC+02:00
Page 4 of 13

Powered by phpBB® Forum Software © phpBB Limited