686 - Goldbach's Conjecture (II)

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

Moderator: Board moderators

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

Post by little joey » Sat Jan 24, 2004 10:32 am

Sorry, it was a typo :oops:

For 543 (I guess that's what you mean) I don't think it's important if you have the same prime listed twice.

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

686 - WA

Post by WR » Tue Feb 10, 2004 5:18 pm

Hi, could anybody please confirm or reject the following results
for problem 686?

input ---> output

22292 ---> 177
30000 ---> 602
32000 ---> 312
100 ---> 6
20 ---> 2
32760 ---> 856
32766 ---> 517

My program is very similar to that for problem 543, but I'm getting
WA for this one.

Maybe somebody has any suggestions?!

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Wed Feb 11, 2004 10:15 am

Last two lines of your outputs are wrong. My solution outputs :
32760 => 857
32766 => 518

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

Post by WR » Wed Feb 11, 2004 1:08 pm

Thanks a lot, DM

haven't found the mistake yet but certainly will.


added:

Silly mistake sure enough (just forgot a prime);
program's not too fast but accepted.

Thanks again

eshika
New poster
Posts: 11
Joined: Sat Oct 02, 2004 12:02 pm
Location: Bangladesh

686:Goldbach's Conjecture (II) WHY WRONG ANSWER?????

Post by eshika » Sat Jan 01, 2005 10:53 am

I have checked the code several times but cannot find out the error. Could anybody suggest?

Code: Select all

//deleted
Last edited by eshika on Sun Jan 02, 2005 10:45 am, edited 1 time in total.

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Sun Jan 02, 2005 2:49 am

Hi eshika

Try this

Input:
4

Output
1

Hope it helps :wink:

eshika
New poster
Posts: 11
Joined: Sat Oct 02, 2004 12:02 pm
Location: Bangladesh

Post by eshika » Sun Jan 02, 2005 10:42 am

Thanks a lot!

pipo
New poster
Posts: 47
Joined: Tue May 11, 2004 6:43 pm
Location: Republic of Korea

686.. why WA ??

Post by pipo » Sun Feb 20, 2005 7:02 pm

greetings...

i sovled 686 problem.. but i got WA...

the solution is very simple...

first.. precalculate 65536 prime numbers..

and then, input a value of sum..

if i is a prime number and sum-i is a prime number, increase counter..

so that print the counter..

and i have tested some inputs.. in my thought the resut is right..

why i got WA ?

my code is...

Code: Select all

#include <stdio.h>

#define MAX		65536

#define TRUE	1
#define FALSE	0

void main(void)
{
	char prime[MAX];
	int i, j;
	int half_value;
	int sum;
	int cnt;
	
	prime[0] = FALSE;
	prime[1] = FALSE;

	for ( i = 2 ; i < MAX ; i++ ) 
	{
		if ( prime[i] == FALSE )
			continue;

		j = i + i;

		while ( j < MAX )
		{
			prime[j] = FALSE;

			j += i;
		}
	}

	while ( 1 ) 
	{
		scanf("%d", &sum);

		if ( sum == 0 ) 
			break;

		cnt = 0;
		half_value = sum / 2;

		for ( i = 2 ; i <= half_value ; i++ ) 
			if ( prime[i] && prime[sum-i]) 
					cnt++;

		printf("%d\n", cnt);
	}	
}

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Mon Feb 28, 2005 3:04 pm

your prime number list generation is wrong
you have to include the loop

Code: Select all

for(i=0;i<MAX;i++)prime[i]=TRUE;
before

Code: Select all

prime[0] = FALSE; 
   prime[1] = FALSE; 

pipo
New poster
Posts: 47
Joined: Tue May 11, 2004 6:43 pm
Location: Republic of Korea

Post by pipo » Mon Feb 28, 2005 5:52 pm

thanks a lot .. emotional blind...

thanks to you, i got AC... :D

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

sample I/O

Post by Sedefcho » Wed Mar 16, 2005 1:44 pm

For anyone who may need some sample I/O

INPUT

Code: Select all

4
6
12
10
14
16
100
1000
1002
10000
22292
32306
32502
32760
32766
0

OUTPUT

Code: Select all

1
1
1
2
2
2
6
28
36
127
177
251
491
857
518

User avatar
tmdrbs6584
Learning poster
Posts: 98
Joined: Sat Jan 21, 2006 12:45 pm
Location: Busan,Corea(Republic of)

686 Goldbach's Conjecture (II) Why TLE???

Post by tmdrbs6584 » Mon Feb 27, 2006 10:33 am

#include<iostream.h>
#include<math.h>
int main(){
int n;
while(cin >> n){
if(n==0) break;
int a[20000]={2,0,},i,j,cnt=1,ccnt=0,cc[20000]={0,},ccc[20000]={0,};
for(i=3;i<n;i++){
int sw=0;
for(j=2;j<=sqrt(i);j++)
if(i%j==0) sw=1;
if(sw==0){
a[cnt]=i;
cnt++;
}
}
for(i=0;i<cnt;i++){
for(j=0;j<cnt;j++){
if(a+a[j]==n){
cc[ccnt]=a;
ccc[ccnt]=a[j];
ccnt++;
}
}
}
cnt=0;
for(i=0;i<ccnt;i++){
for(j=0;j<ccnt;j++){
if(i!=j)
if(cc==ccc[j] && ccc==cc[j]){cc=0; ccc=0;}
}
}
for(i=0;i<ccnt;i++)
if(cc!=0) cnt++;
cout << cnt << endl;
}
return 0;
}

User avatar
tmdrbs6584
Learning poster
Posts: 98
Joined: Sat Jan 21, 2006 12:45 pm
Location: Busan,Corea(Republic of)

Post by tmdrbs6584 » Mon Feb 27, 2006 10:43 am

This is my source, but why TLE??
#include<iostream.h>
#include<math.h>
int main(){
int n;
while(cin >> n){
if(n==0) break;
int a[20000]={2,0,},i,j,cnt=1,ccnt=0,cc[20000]={0,},ccc[20000]={0,};
for(i=3;i<n;i++){
int sw=0;
for(j=2;j<=sqrt(i);j++)
if(i%j==0) sw=1;
if(sw==0){
a[cnt]=i;
cnt++;
}
}
for(i=0;i<cnt;i++){
for(j=0;j<cnt;j++){
if(a+a[j]==n){
cc[ccnt]=a;
ccc[ccnt]=a[j];
ccnt++;
}
}
}
cnt=0;
for(i=0;i<ccnt;i++){
for(j=0;j<ccnt;j++){
if(i!=j)
if(cc==ccc[j] && ccc==cc[j]){cc=0; ccc=0;}
}
}
for(i=0;i<ccnt;i++)
if(cc!=0) cnt++;
cout << cnt << endl;
}
return 0;
}
And Here is my test data,
INPUT:
1 2 3 4 5 6 7 8 9 10 20 30 40 50 60 70 80 90 100 200 300 400 500 600
700 800 900 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000
20000 30000
OUTPUT:
0 0 0 1 1 1 1 1 1 2 2 3 3 4 6 5 4 9 6 8 21 14 13 32 24 21 48 28 37 104 65
76 178 119 106 242 127 231 602

Why TLE??

User avatar
tmdrbs6584
Learning poster
Posts: 98
Joined: Sat Jan 21, 2006 12:45 pm
Location: Busan,Corea(Republic of)

Oh,,

Post by tmdrbs6584 » Mon Feb 27, 2006 10:47 am

Oh, I got AC,,
I changed my code
if(i%j==0) sw=1;
to
if(i%j==0){sw=1; break;}
Thanks

User avatar
tmdrbs6584
Learning poster
Posts: 98
Joined: Sat Jan 21, 2006 12:45 pm
Location: Busan,Corea(Republic of)

Oops!

Post by tmdrbs6584 » Mon Feb 27, 2006 10:47 am

Oh, I got AC,,
I changed my code
if(i%j==0) sw=1;
to
if(i%j==0){sw=1; break;}
Thanks

Post Reply

Return to “Volume 6 (600-699)”