Page 1 of 3

10820 - Send a Table

Posted: Sat Mar 05, 2005 9:25 pm
by mido
Seems literally everyone was able to solve A...any hints would be appreciated....

Posted: Sat Mar 05, 2005 11:53 pm
by marian

Posted: Wed Mar 09, 2005 6:37 am
by sumankar
Can someone give output for the following :

Code: Select all

1
100
1000
10000
50000
My outputs are:

Code: Select all

1
5647
550769
54866397
3089251479
Regards,
Suman.

Posted: Wed Mar 09, 2005 6:39 am
by Observer
Your output is not correct. However, since I haven't got my code with me now, I can't give you the correct one...

The output for 50000 should be something like 15xxxxxxxx. :wink:

P.S. about 30% of submissions to this task is contributed my me~ :P

Posted: Wed Mar 09, 2005 8:20 am
by Cho
sumankar wrote:Can someone give output for the following :

Code: Select all

1
100
1000
10000
50000
Correct output:

Code: Select all

1
6087
608383
60794971
1519848527

Posted: Wed Mar 09, 2005 10:46 am
by sumankar
Cho and Observer,

Thanks a zillion tonnes, i owe that 6th place to you guys. :D

I forgot

premature optimization is the root of all evil
- Knuth


regards,
Suman.

Posted: Wed Mar 09, 2005 4:06 pm
by Cosmin.ro
You can do it with an algo similar to the sieve of Eratosthenes.

Posted: Wed Mar 09, 2005 4:08 pm
by sumankar
Cosmin.ro

If that was for me, my answer would be - that's exactly what I did :D

Regards,
Suman

Posted: Wed Mar 09, 2005 4:31 pm
by Observer
Tried 20 more times and get down to 0.00.008... Dunno how to optimize it anymore. Maybe some look-up tables? (Dun even know what to put in the table) :wink:

P.S. sumankar, sorry if my reply wasn't that useful... :P
P.P.S. Lawrence (..) has just achieved 0.00.000! ho ging ah~~~

Posted: Thu Mar 10, 2005 6:21 am
by sumankar
Observer wrote:Tried 20 more times and get down to 0.00.008... Dunno how to optimize it anymore. Maybe some look-up tables? (Dun even know what to put in the table) :wink:
Look - up Tables -huh?Have the totient functions calculated for all n
and calculating totient functions would mean the answers can be calculated easily - store them in a table and go on printf'ing happily ever after.
P.S. sumankar, sorry if my reply wasn't that useful... :P
No it was, believe me.
P.P.S. Lawrence (..) has just achieved 0.00.000! ho ging ah~~~
Let's hope he comes down and explains here ...

Regards,
Suman.

Posted: Thu Mar 10, 2005 6:33 am
by Observer
sumankar wrote:Look - up Tables -huh?Have the totient functions calculated for all n and calculating totient functions would mean the answers can be calculated easily - store them in a table and go on printf'ing happily ever after.
Please try it then ~ :D :D :D

Don't think ..'s doing this way though.

- EDIT -

P.S. I wonder what other PASCAL programmers are using. My PASCAL solution can get this time:
http://acm.uva.es/cgi-bin/OnlineJudge?S ... 42:1.00:60::
which is about ten times faster than the current fastest PASCAL solution in ranklist... And I haven't used any precalculation :P

Posted: Sat Mar 12, 2005 6:27 pm
by mido
Forgot to say this: Thanks, marian

Compile Error C++ 10820

Posted: Wed Mar 16, 2005 11:41 am
by AndyGee
Its my first program in C++.
I run the following code on the VC++, and it was ok.
But the judge give me "Compile Error".
Can anyone help me?

Code: Select all

#include <stdio.h>
//using namespace std; 

int p[50001];
int pc[50001];
long f[50001];



void PrepareArray()
{
   long j;
   for (long i = 2;  i <= 50000; i++) {
      pc[i] = pc[i-1];
		if (p[i]) continue;
      pc[i] = pc[i] + 1;
      j = 2 * i;
      for (; j <= 50000; j=j+i) p[j]++;
      
   }
   
}

void main()
{
   
   for (long i = 1; i <= 50000 ; i++) p[i] = 0;
   for (i = 1; i <= 50000 ; i++) pc[i] = 0;
   for (i = 1; i <= 50000 ; i++) f[i] = 0;
   PrepareArray();

   long max = 1;
   f[1] = 1;
   int N = 0;
   while (scanf("%d\n",&N)==1){
	   if (N > max) {
		  for (i = max + 1; i <= N; i++)
			 if (p[i]) { f[i] = f[i-1] + (pc[i] - p[i] + 1)*2; }
			 else { f[i] = f[i-1] + (i - 1) * 2; }
		  max = N;
	   }
      printf("%d\n",f[N]);
   }

}

Posted: Wed Mar 16, 2005 11:44 am
by AndyGee
I try to use

Code: Select all

#include <cstdio>
using namespace std; 
but CE again :(

ooopsii daisy...

Posted: Wed Mar 16, 2005 12:00 pm
by sohel
Consider this part of your code:

Code: Select all

for (long i = 1; i <= 50000 ; i++) p[i] = 0; 
   for (i = 1; i <= 50000 ; i++) pc[i] = 0; 
The scope of i is only within the first for()..
.. for the second for, i has not been declared..

change it to something like


Code: Select all

long i;
for (i = 1; i <= 50000 ; i++) p[i] = 0; 
   for (i = 1; i <= 50000 ; i++) pc[i] = 0; 
And that should avoid CE... :)