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

Post Reply
Backbone
New poster
Posts: 5
Joined: Sun May 21, 2006 8:40 am

P- 406 PRIME CUTS WA!!! Can anybody help me?? plz

Post 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!! :)

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post 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.

Backbone
New poster
Posts: 5
Joined: Sun May 21, 2006 8:40 am

I still have an error

Post 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

eyeabhi
New poster
Posts: 11
Joined: Fri Apr 28, 2006 4:16 pm
Location: Bangladesh
Contact:

WA 406 -- All the input output i found all r correct

Post 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.
Abhishek Roy
Undergraduate Student,
Department of Computer Science and Engineering,
Bangladesh University of Engineering and Technology, Dhaka.

sohel_acm
New poster
Posts: 8
Joined: Fri May 19, 2006 11:27 pm
Location: Bangladesh

Post 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.
Love programmers,help programmers.

eyeabhi
New poster
Posts: 11
Joined: Fri Apr 28, 2006 4:16 pm
Location: Bangladesh
Contact:

Thank u ... I got it

Post by eyeabhi »

My program had a bug, i fixed it and got AC. thank u very much for ur input/output.
Abhishek Roy
Undergraduate Student,
Department of Computer Science and Engineering,
Bangladesh University of Engineering and Technology, Dhaka.

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

406 prime cuts WA

Post 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.

Artikali
Learning poster
Posts: 68
Joined: Wed Sep 21, 2005 5:27 pm

Post 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

linux
Learning poster
Posts: 56
Joined: Sat Jul 01, 2006 12:21 pm
Location: CA-95054
Contact:

About P.E.

Post by linux »

Just print double new line and get accepted.

Code: Select all

printf("\n\n");
Hope understand. GL. :lol:
Solving for fun..

unaben
New poster
Posts: 12
Joined: Mon Jul 10, 2006 10:47 pm

406 WA

Post by unaben »

I am getting WA all the time with my code. :o Could someone plz help :wink:

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!

alan0101
New poster
Posts: 1
Joined: Thu Sep 14, 2006 4:59 pm

406 WA... why.. ??

Post 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;

}


little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

There are already many threads for this problem. Please use one of these.

wensi
New poster
Posts: 2
Joined: Sat Nov 25, 2006 5:49 pm

406 TLE Prime Cuts

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

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post 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
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

wensi
New poster
Posts: 2
Joined: Sat Nov 25, 2006 5:49 pm

Post 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...

Post Reply

Return to “Volume 4 (400-499)”