406 - Prime Cuts

All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

406 - Prime Cuts

Post by asif_rahman0 » Tue May 17, 2005 6:44 pm

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

User avatar
Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

Reply On 406

Post by Rocky » Thu May 19, 2005 8:07 am

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
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Thaks for help

Post by asif_rahman0 » Sat May 21, 2005 7:09 pm

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

sfwejfish
New poster
Posts: 2
Joined: Wed Aug 10, 2005 7:19 am
Contact:

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

Post by sfwejfish » Wed Aug 10, 2005 7:21 am

#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
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Sun Aug 14, 2005 2:57 pm

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.
Last edited by chunyi81 on Sat Mar 11, 2006 5:10 am, edited 1 time in total.

sfwejfish
New poster
Posts: 2
Joined: Wed Aug 10, 2005 7:19 am
Contact:

Post by sfwejfish » Mon Aug 15, 2005 1:27 am

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
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

406 WA.....

Post by Wei-Ming Chen » Mon Nov 14, 2005 2:35 pm

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
New poster
Posts: 1
Joined: Sun Nov 27, 2005 4:30 pm

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

Post by hinyinlam » Sun Nov 27, 2005 4:45 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Dec 23, 2005 9:26 pm

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

Input:

Code: Select all

997 1
Output:

Code: Select all

433
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Dec 23, 2005 9:29 pm

You need primes less than 1000 only. Why you are generating primes less than 1000010? So you are getting TLE.
Ami ekhono shopno dekhi...
HomePage

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Dec 23, 2005 9:43 pm

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.
Ami ekhono shopno dekhi...
HomePage

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Dec 23, 2005 9:58 pm

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.
Ami ekhono shopno dekhi...
HomePage

kolpobilashi
Learning poster
Posts: 54
Joined: Mon Jan 02, 2006 3:06 am
Location: Dhaka,Bangladesh
Contact:

406 got TLE,help me!!

Post by kolpobilashi » Tue Jan 17, 2006 5:07 pm

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]
Sanjana

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Re: 406 got TLE,help me!!

Post by mamun » Tue Jan 17, 2006 5:25 pm

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?

kolpobilashi
Learning poster
Posts: 54
Joined: Mon Jan 02, 2006 3:06 am
Location: Dhaka,Bangladesh
Contact:

hmmmm....now wat?!

Post by kolpobilashi » Tue Jan 17, 2006 9:45 pm

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..... :(
Sanjana

Post Reply

Return to “Volume 4 (400-499)”