11190 - Series of Powers

[leocm]

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]

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]

For example, in this way:

Code: Select all

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

[domino]

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

[mf]

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

[leocm]

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]

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

[leocm]

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

Can you help me mf?
TY.

[helloneo]

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

Code: Select all

10 10 1000000
-1 -1 -1

[sclo]

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]

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]

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

[sclo]

Try this case:

Code: Select all

0 0 15000000

[Jan]

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.

[arsalan_mousavian]

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)