10820 - Send a Table

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

Moderator: Board moderators

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

10820 - Send a Table

Post by mido » Sat Mar 05, 2005 9:25 pm

Seems literally everyone was able to solve A...any hints would be appreciated....

marian
New poster
Posts: 30
Joined: Sun Oct 27, 2002 4:01 pm
Contact:

Post by marian » Sat Mar 05, 2005 11:53 pm


sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar » Wed Mar 09, 2005 6:37 am

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.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Wed Mar 09, 2005 6:39 am

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
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Wed Mar 09, 2005 8:20 am

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

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar » Wed Mar 09, 2005 10:46 am

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.

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am

Post by Cosmin.ro » Wed Mar 09, 2005 4:06 pm

You can do it with an algo similar to the sieve of Eratosthenes.

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar » Wed Mar 09, 2005 4:08 pm

Cosmin.ro

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

Regards,
Suman

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Wed Mar 09, 2005 4:31 pm

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~~~
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar » Thu Mar 10, 2005 6:21 am

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.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Thu Mar 10, 2005 6:33 am

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
Last edited by Observer on Thu Mar 24, 2005 6:27 pm, edited 4 times in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

Post by mido » Sat Mar 12, 2005 6:27 pm

Forgot to say this: Thanks, marian

AndyGee
New poster
Posts: 8
Joined: Sat Nov 13, 2004 3:11 pm
Location: KG
Contact:

Compile Error C++ 10820

Post by AndyGee » Wed Mar 16, 2005 11:41 am

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]);
   }

}

AndyGee
New poster
Posts: 8
Joined: Sat Nov 13, 2004 3:11 pm
Location: KG
Contact:

Post by AndyGee » Wed Mar 16, 2005 11:44 am

I try to use

Code: Select all

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

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

ooopsii daisy...

Post by sohel » Wed Mar 16, 2005 12:00 pm

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... :)

Post Reply

Return to “Volume 108 (10800-10899)”