Page 6 of 13
P- 406 PRIME CUTS WA!!! Can anybody help me?? plz
Posted: Sun May 21, 2006 9:19 am
by Backbone
Hi everybody, I've tried a lot of times and I still got a WA in 406, I'm testing all the inputs that I found, but WA!!, here is the code!!..
C++:
#include<iostream>
#include<stdlib.h>
using namespace std;
int primes(int N)
{
int prime=1,numprimes=0,i,isprime=1;
while(prime<=N)
{
for(i=2; i<prime; i++)
if(prime%i==0)
{
isprime=0;
i=prime;
}
if(isprime) numprimes++;
prime++;
isprime=1;
}
return numprimes;
}
int *saveprimes(int nprimes,int N)
{
int *array;
array=(int *)malloc(sizeof(nprimes));
int prime=1,numprimes=0,i,cont=0,isprime=1;
while(prime<=N)
{
for(i=2; i<prime; i++)
if(prime%i==0)
{
isprime=0;
i=prime;
}
if(isprime)
{
*(array+cont)=prime;
cont++;
numprimes++;
}
prime++;
isprime=1;
}
return array;
}
void impcentro(int *array, int C,int nprimes)
{
int centro,i,izq,der;
centro=nprimes/2;
if(nprimes%2!=0)
{
C=(C*2)-1;
izq=centro-(C-1)/2;
der=centro+(C-1)/2;
}
else
{
C=C*2;
izq=centro-C/2;
der=centro+(C-1)/2;
}
if(C>nprimes)
{
izq=0;
der=nprimes-1;
}
for(i=izq; i<=der;i++)
cout<<" "<<*(array+i);
cout<<"\n";
free(array);
}
main()
{
int N,C,nprimes,*primos;
while(cin>>N>>C && N>=1 && C>=1 && C<=N)
{
cout<<N<<" "<<C<<":";
nprimes=primes(N);
primos=saveprimes(nprimes,N);
impcentro(primos,C,nprimes);
}
}
Thnkz for Help me!!
Posted: Sun May 21, 2006 3:41 pm
by chunyi81
Check the output specifications again:
For each input set, you should print the number N beginning in column 1 followed by a space, then by the number C, then by a colon ( : ), and then by the center numbers from the list of prime numbers as defined above. If the size of the center list exceeds the limits of the list of prime numbers between 1 and N, the list of prime numbers between 1 and N (inclusive) should be printed. Each number from the center of the list should be preceded by exactly one blank. Each line of output should be followed by a blank line. Hence, your output should follow the exact format shown in the sample output.
in particular pay attention to the sentence highlighted in bold.
I still have an error
Posted: Sun May 21, 2006 8:14 pm
by Backbone
Hello!, thankz for reply, but I have solved the blank line problem and I still have WA!!, why??, I've tested a lot of inputs and all are correct... thnkz
WA 406 -- All the input output i found all r correct
Posted: Mon May 22, 2006 10:19 pm
by eyeabhi
Code: Select all
/*
Prime Cuts
*/
#include <stdio.h>
#include <iostream.h>
#include <math.h>
#define MAX 2000
void sieve(int *p)
{
int count;
int i, j;
count = (int)sqrt(MAX) + 1;
for(i = 4; i < MAX; i += 2)
p[i] = 1; // means i is not prime
p[2] = 0; // means 2 is prime
for(i = 3; i < MAX; i += 2)
p[i] = 0; // i is suspected to be prime
for(i = 3; i <= count; i += 2)
if(p[i] == 0)
for(j = 2 * i; j < MAX; j += i)
p[j] = 1; // means j is not prime
}
void main()
{
int i, j, x, n, d;
int c[MAX];
int primes[MAX];
sieve(c);
// bool firsttime = true;
primes[1] = 1;
primes[2] = 2;
primes[3] = 3;
// creating list of prime numbers
for(i = 4, x = 4; i < MAX; i++){
if(c[i] == 0){
primes[x] = i;
x++;
}
}
while(scanf("%d %d", &n, &d) == 2){
printf("%d %d:", n, d);
for(i = 1; primes[i] < n; i++)
;
if(primes[i] != n)
i--;
if(i % 2 == 0){
x = 2 * d;
}
else{
x = 2 * d - 1;
}
i = i / 2 - x / 2 + 1;
for(j = 0; j < x && primes[i + j] <= n; j++){
if(i + j < 1)
continue;
printf(" %d", primes[i + j]);
}
printf("\n\n");
}
}
i tested all the i/o i found in 406 threads. they give correct answer. can anyone tell whts wrng?
thanx.
Posted: Tue May 23, 2006 8:37 pm
by sohel_acm
Hi Abhi you can try these input set.
Code: Select all
41 67
334 0
169 24
478 58
962 64
705 45
281 27
961 91
995 42
827 36
391 4
902 53
292 82
421 16
718 95
447 26
771 38
869 12
667 99
35 94
703 11
322 33
673 64
141 11
253 68
547 44
662 57
37 59
723 41
529 78
The correct output:
Code: Select all
41 67: 1 2 3 5 7 11 13 17 19 23 29 31 37 41
334 0:
169 24: 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
478 58: 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
962 64: 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
705 45: 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
281 27: 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
961 91: 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
995 42: 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
827 36: 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
391 4: 149 151 157 163 167 173 179 181
902 53: 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
292 82: 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
421 16: 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
718 95: 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
447 26: 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
771 38: 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
869 12: 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443
667 99: 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
35 94: 1 2 3 5 7 11 13 17 19 23 29 31
703 11: 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367
322 33: 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
673 64: 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
141 11: 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103
253 68: 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
547 44: 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
662 57: 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
37 59: 1 2 3 5 7 11 13 17 19 23 29 31 37
723 41: 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
529 78: 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
Best Of Luck.
Thank u ... I got it
Posted: Fri May 26, 2006 2:45 pm
by eyeabhi
My program had a bug, i fixed it and got AC. thank u very much for ur input/output.
406 prime cuts WA
Posted: Sun Jul 02, 2006 3:02 pm
by ayeshapakhi
i got at least 5 WA. plz help me
Code: Select all
/* !NOT ACCEPTED!!!!!!!!Primes Cut 406*/ //Submit again
#include <stdio.h>
#include <math.h>
#define L 1
#define U 100001
#define N 50000
long primes[N];
long c=0;
bool all[U];
long count[U];
void seive(void);
void main()
{
freopen("406.in","r",stdin);
freopen("out406.txt","w",stdout);
long num1,num2,i,temp,start,end;
for(i=0; i<U; i++)
{
all[i]=false;
count[i]=0;
}
seive();
while((scanf("%ld%ld",&num1,&num2))==2)
{
for(i=num1; ; i--)
{
if(all[i])
{
temp=count[i];
break;
}
}
if(temp%2==0)
{
if(2*num2>=num1)
{
start=0;
end=temp;
}
else
{
start=temp/2-num2;
end=temp/2+num2;
}
}
else
{
if((2*num2-1)>=num1)
{
start=0;
end=temp;
}
else
{
start=temp/2-num2+1;
end=temp/2+num2;
}
}
printf("%ld %ld: ",num1,num2);
for(i=start; i<end; i++) printf("%ld ",primes[i]);
printf("\n\n");
}
}
void seive(void)
{
int i,j,d;
d=U-L+2;
bool *flag=new bool[d];
for(i=0; i<d; i++) flag[i]=true;
for(i=(L%2!=0); i<d; i+=2) flag[i]=false;
for(i=3; i<sqrt(U); i+=2)
{
if(i>L && !flag[i-L]) continue;
j=L/i*i;
if(j<L) j+=i;
if(j==i) j+=i;
j-=L;
for( ; j<d; j+=i) flag[j]=false;
if(L<=1) flag[1-L]=true;
if(L<=2) flag[2-L]=true;
}
c=0;
for(i=0; i<d; i++)
if(flag[i])
{
primes[c++]=L+i;
all[L+i]=true;
count[L+i]=c;
}
return;
}
thanks for any help.
Posted: Sun Jul 02, 2006 7:12 pm
by Artikali
460 46: 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
460 47: 0 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
460 48: 0 0 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
460 49: 0 0 0 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
460 50: 0 0 0 0 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
460 51: 0 0 0 0 0 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
460 52: 0 0 0 0 0 0 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
460 53: 0 0 0 0 0 0 0 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
460 168: -1543218801 2109923008 516352251 1518921630 -1086549673 404915024 1650805582 -1349549059 293442566 -1612829212 80270030 181970653 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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 1009 1013 1019 1021 1031 1033 1039 1049 1051 1061 1063 1069 1087 1091 1093 1097
About P.E.
Posted: Tue Jul 18, 2006 3:05 pm
by linux
Just print double new line and get accepted.
Hope understand. GL.
406 WA
Posted: Sun Aug 27, 2006 12:24 am
by unaben
I am getting WA all the time with my code.
Could someone plz help
Here is my code:
#include<iostream>
using namespace std;
int main()
{
bool *a = new bool[1001];
int n = 1000;
int primes[1000];
primes[0]=1;
int prim=1;
a[0] = 0;
a[1] = 1;
for(int i=2; i<=1000; i++)
a
=1;
int p = 2;
while(p*p<=n)
{
int j=p*p;
primes[prim]=p;
prim++;
while(j<=n)
{
a[j]=0;
j +=p;
}
bool ok = true;
for(int k=p+1; ok and k<=n; k++)
{
if(a[k]==1)
{
ok = false;
p++;
}
else
p++;
}
}
for(int h=p+1; h<=n; h++)
{
if(a[h]==1)
{
primes[prim]=h;
prim++;
}
}
int num, c;
while(cin>>num>>c)
{
bool go = true;
int array[500];
int st=0;
for(int z=0; go and z<prim; z++)
{
if(primes[z]<=num)
st++;
else
go = false;
}
int hold, index, zeros;
cout<<num<<" "<<c<<": ";
if(st%2==0)
{
if(c*2<=st)
{
hold = st - (c*2);
index = hold/2;
for(int f=index; f<index+c*2; f++)
cout<<primes[f]<<" ";
cout<<endl;
}
else
{
for(int m=0; m<st; m++)
cout<<primes[m]<<" ";
cout<<endl;
}
}
else
{
if(((c*2)-1)<=st)
{
hold = st - (c*2)-1;
index = hold/2;
for(int f=index+1; f<=(index-1+c*2); f++)
cout<<primes[f]<<" ";
cout<<endl;
}
else
{
for(int m=0; m<st; m++)
cout<<primes[m]<<" ";
cout<<endl;
}
}
cout<<endl;
}
}
Thanx in advance!
406 WA... why.. ??
Posted: Thu Sep 14, 2006 5:03 pm
by alan0101
Code: Select all
#include <stdlib.h>
#include <stdio.h>
#include "math.h"
int main()
{
int* p;
p = new int[2001];
int bigarray[400];
int c;
int k, j;
p[1] = 0;
c = (int) sqrt(2000.0) + 1;
for(k = 4; k < 2000; k += 2)
p[i] = 1;
p[2] = 0; /////// it is prime
for(k = 3; i < 2000; k += 2)
p[k] = 0; ///// might be prime
for(k = 3; k <= c; k += 2)
if(p[k] == 0)
for(j = 2 * i; j < 2000; j += k)
p[j] = 1; /////// j = !prime
int length; // select those prime numbas out
length = 0;
for (int i = 1; i <= 2000; i++)
{
if (p[i] == 0)
{
length++;
bigarray[length] = i;
}
}
delete [] p; // release memory
int NT, NI;
while ( scanf("%d %d\n", &NT, &NI ) == 2)
{
int y;
int up, low;
// y = 105;
up = length;
low = 1;
if (NT == 2000)
{
y = length;
}
else
{
while (1) // the binary search to get the center index
{
y = (up + low) /2;
if (bigarray[y] > NT )
up = y;
else
low = y;
if (bigarray[y] <= NT && bigarray[y+1] > NT)
break;
}
}
printf("%d %d:", NT, NI);
int k;
k = ((y) % 2);
int haha;
haha = NI;
if (k == 1) haha = NI - 1; else haha = NI;
if (k == 1) // if the index is odd then k = 1,
{
// printf("haha!");
for (int i = (y-1)/2- haha+1; i <= (y-1)/2; i++)
{
if (i < 1) i = 1;
if (i > y) break;
printf(" %d", bigarray[i]);
}
printf(" %d", bigarray[(y-1)/2+1]);
for (int i = (y-1)/2 +2; i <= (y-1)/2 + haha+1; i++)
{
if (i < 1) i = 1;
if (i > y) break;
printf(" %d", bigarray[i]);
}
}
else
{ // index = even..
for (int i =y/2 - haha+1; i <= y/2; i++)
{
if (i < 1) i = 1;
if (i > y) break;
printf(" %d", bigarray[i]);
}
for (int i = y/2+1; i <= y/2 + haha; i++)
{
if (i < 1) i = 1;
if (i > y) break;
printf(" %d", bigarray[i]);
}
}
printf("\n\n");
}
// system("PAUSE");
return 0;
}
Posted: Thu Sep 14, 2006 5:13 pm
by little joey
There are already many threads for this problem. Please use one of these.
406 TLE Prime Cuts
Posted: Sat Nov 25, 2006 5:52 pm
by wensi
I tried all the inputs from the forum and all worked, still getting tle, could anyone help?
also i tried to add braces around the if/else statements but didnt change.
Code: Select all
#include <iostream>
#include <vector>
using namespace std;
bool prime(int n);
int main()
{
int i,n,c,temp;
vector<int> v;
while (cin>>n>>c)
{
v.clear();
for (i=1;i<=n;i++)
if (prime(i)==true)
v.push_back(i);
cout<<n<<" "<<c<<": ";
temp=c;
if ((v.size()&1)==0)
c*=2;
else
c=c*2-1;
if (c>v.size())
for (i=0;i<v.size();i++)
cout<<v[i]<<" ";
else
if ((v.size()&1)==0)
for (i=v.size()/2-c/2;i<v.size()/2+c/2;i++)
cout<<v[i]<<" ";
else
for (i=v.size()/2-c/2;i<=v.size()/2+c/2;i++)
cout<<v[i]<<" ";
cout<<endl<<endl;
}
return 0;
}
bool prime(int n)
{
int i=1;
int c=0;
for (i;i<=n;i++)
if (n%i==0)
c++;
if (c>2)
return false;
return true;
}
Posted: Sat Nov 25, 2006 6:39 pm
by ayon
your prime() function is extremely extremely extremely slower. have a look at
http://www.comp.nus.edu.sg/~stevenha/pr ... atics.html
for some faster methods
Posted: Sun Nov 26, 2006 3:50 am
by wensi
thx, did everything i can to improve the speed, and finally got AC, and it is solved in 3.9 seconds. in the question it says N<=1000, I still dont understand why would that take so long to finish...