11190 - Series of Powers

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

Moderator: Board moderators

leocm
New poster
Posts: 22
Joined: Fri Jul 21, 2006 9:44 am
Location: Brasil

Formatted output (printf)

Post by leocm » Sun Mar 04, 2007 8:34 am

How can I output in C a number in this format:

0.ddddddedddddddddd

examples:
0.149143e0000000011
0.406971e0000000118

I need this to make the Problem E - Series of Powers - of the running contest.

At the moment of my question: http://online-judge.uva.es/contest/data ... set/e.html

leocm
New poster
Posts: 22
Joined: Fri Jul 21, 2006 9:44 am
Location: Brasil

11190 - Series of Powers

Post by leocm » Sun Mar 04, 2007 8:36 am

This problem will be here soon, so, how can I output in C a number in this format:

0.ddddddedddddddddd

examples:
0.149143e0000000011
0.406971e0000000118

I need this to make the Problem E - Series of Powers - of the running contest.

At the moment of my question: http://online-judge.uva.es/contest/data ... set/e.html

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sun Mar 04, 2007 8:42 am

For example, in this way:

Code: Select all

double mantissa; long long exponent;
...
printf("%.6fe%.10lld\n", mantissa, exponent);

domino
New poster
Posts: 19
Joined: Thu Dec 25, 2003 6:01 pm

Post by domino » Sun Mar 04, 2007 3:20 pm

How do you solve this without getting TLE? I tried an O((H-L)*lgK) approach but it did not fit the timelimit.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sun Mar 04, 2007 3:28 pm

I've used log10(), floor() and pow() from math.h to do conversions, nothing fancy. It runs in ~1.2 seconds.

leocm
New poster
Posts: 22
Joined: Fri Jul 21, 2006 9:44 am
Location: Brasil

Post by leocm » Sun Mar 04, 2007 6:40 pm

What is WRONG?

Code: Select all

#include <stdio.h>
#include <math.h>

int main()
{
   long long int cases = 1, i, l, h, k, exponent;
   double mantissa, result; 
   
   while ( scanf ("%lld %lld %lld", &l, &h, &k ) == 3 && ( l != -1 || h != -1 || k != -1 ) )
   {
      mantissa = 0.0;
      for ( i = l; i <= h; i++ )
         mantissa += pow( (double) i, (double) k );   

      /* calculate the number of digits in the integer part */  
      if ( mantissa == 0 )
         exponent = 1; 
      else
         exponent = floor( log10( mantissa ) ) + 1;
      
      /* makes mantissa be a number between 0 and 1 */
      mantissa = mantissa / pow (10, exponent);
                 
      printf("Case %04lld: %lfe%010lld\n", cases++, mantissa, exponent);
   }  
   return 0;
}
I got WA two times!

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sun Mar 04, 2007 7:08 pm

Try a simple test with a really big answer, e.g. 10 10 1000000.
Your program's output certainly doesn't look right.

leocm
New poster
Posts: 22
Joined: Fri Jul 21, 2006 9:44 am
Location: Brasil

Post by leocm » Sun Mar 04, 2007 7:20 pm

The problem is greater than I thought!
So, I really have no idea how to do this?

Can you help me mf?
TY.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Sun Mar 04, 2007 7:20 pm

Hello..~
What is the correct answer for this input..?

Code: Select all

10 10 1000000
-1 -1 -1

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sun Mar 04, 2007 7:23 pm

helloneo wrote:Hello..~
What is the correct answer for this input..?

Code: Select all

10 10 1000000
-1 -1 -1
What do you expect?

Code: Select all

Case 0001: 0.100000e0001000001

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sun Mar 04, 2007 7:25 pm

Here's a hint for solving this problem. Think about how to simulate floating point arithmetic in base 10 using long double for the mantisa and long long for the exponent. (instead of base 2). I think actually double is enough for the mantisa, but I used long double anyway.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Sun Mar 04, 2007 7:41 pm

Thanks sclo.. finally got AC..
I got many WAs.. and it turned out precision error.. :cry:

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sun Mar 04, 2007 7:43 pm

Try this case:

Code: Select all

0 0 15000000

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Mar 04, 2007 11:08 pm

I m currently getting WA. Can anyone verify the I/O sets?

Thanks in advance.

Input:

Code: Select all

20580 21320 22531
13675 13995 25791
13377 14375 16587
21604 22093 19632
29744 30132 26611
18718 19637 18260
5927 6536 28120
21479 22195 6301
21396 22249 11459
20830 21423 30807
29849 30703 24273
26160 26454 12055
26333 26479 4230
10471 10899 10560
22241 22662 22689
16366 16399 26686
2270 2599 32262
10000000 10000000 10000000
0 0 1
-1 -1 -1
Output:

Code: Select all

Case 0001: 0.122988e0000097533
Case 0002: 0.727785e0000106929
Case 0003: 0.254694e0000068963
Case 0004: 0.434673e0000085287
Case 0005: 0.441282e0000119192
Case 0006: 0.588847e0000078392
Case 0007: 0.380698e0000107287
Case 0008: 0.229441e0000027387
Case 0009: 0.168328e0000049817
Case 0010: 0.352143e0000133422
Case 0011: 0.400248e0000108918
Case 0012: 0.371289e0000053314
Case 0013: 0.506262e0000018710
Case 0014: 0.102396e0000042636
Case 0015: 0.363535e0000098818
Case 0016: 0.514293e0000112477
Case 0017: 0.302128e0000110169
Case 0018: 0.100000e0070000001
Case 0019: 0.000000e0000000001
EDIT : Corrected the output.
Last edited by Jan on Mon Mar 05, 2007 12:22 am, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Sun Mar 04, 2007 11:13 pm

sclo wrote:Try this case:

Code: Select all

0 0 15000000
thanks a lot for your testcase, the only testcase that cause me lots of TLEs during the contest was that testcase, and my solution complexity is O(n*logk)
Last edited by arsalan_mousavian on Sun Mar 04, 2007 11:45 pm, edited 1 time in total.
In being unlucky I have the record.

Post Reply

Return to “Volume 111 (11100-11199)”