406 - Prime Cuts
Moderator: Board moderators
-
- Experienced poster
- Posts: 209
- Joined: Sun Jan 16, 2005 6:22 pm
406 - Prime Cuts
I can't understand the problem 406(Prime Cuts).Can anybody tell me what to do?Plz help me.
Reply On 406
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
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
-
- Experienced poster
- Posts: 209
- Joined: Sun Jan 16, 2005 6:22 pm
Thaks for help
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...
#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?
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?
Your code fails for the following input:
Input:
Correct output:
Your program output:
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.
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
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
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
Last edited by chunyi81 on Sat Mar 11, 2006 5:10 am, edited 1 time in total.
-
- Experienced poster
- Posts: 122
- Joined: Sun Nov 13, 2005 10:25 am
- Location: Taiwan
406 WA.....
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;
}
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
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:
OR
??????
Code one: Store all things first then calculate it
Code two: Calculate when there's input

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;
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: 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;
}

Your code is almost ok. Finally I got your error...
Input:
Output:
Hope it helps.
Input:
Code: Select all
997 1
Code: Select all
433
Ami ekhono shopno dekhi...
HomePage
HomePage
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
HomePage
Your code has a lot of errors.
Input:
Output:
(The output is in one line)
Hope it works.
Input:
Code: Select all
900 79
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
Hope it works.
Ami ekhono shopno dekhi...
HomePage
HomePage
I used the following method...
Change the following lines..
And add a new line after each test case.
Hope it works.
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
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
Hope it works.
Ami ekhono shopno dekhi...
HomePage
HomePage
-
- Learning poster
- Posts: 54
- Joined: Mon Jan 02, 2006 3:06 am
- Location: Dhaka,Bangladesh
- Contact:
406 got TLE,help me!!
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]

[/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;
}

Sanjana
Re: 406 got TLE,help me!!
Nice English!!!kolpobilashi wrote:i got TLE 4 dis code,and cant get the reason, anybody tell me y n wats de solution.....![]()

Code: Select all
for(i=0;i<=1003;i++)
ch1[i]=isPrime(i);
-
- Learning poster
- Posts: 54
- Joined: Mon Jan 02, 2006 3:06 am
- Location: Dhaka,Bangladesh
- Contact:
hmmmm....now wat?!
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