PONY6 - Toward Infinity

no tags 

Story: Twilight Sparkle was working on some formulas when she came across a strange pattern.

When she added 1/2 + 1/4 + 1/8 + ..., she saw that it kept getting closer and closer to 1.

She was able to figure out that problem and a few more, but there are others that are too difficult. She needs your help.

Problem Statement

Given k and r, integers, find

Sum from n = 1 to infinity of n^k / r^n.

Also you must output the exact value, as a fraction in lowest terms.


You will be given a number T on the first line. The following T lines will be of the form

S k r

where S is a String label with no spaces, and both k and r are as described above.


Your output will contain T lines of the form

S N / D

where S is the label you were given in the input, N is the numerator of the answer, and D is the denominator. D may be 1.

To be more precise, if the fraction is negative, then output the negative sign next to N.


Case1: 0 2
Case2: 0 3
Case3: 0 -3
Label: 2 9
Otherlabel: 12 16
Biggest: 50 -555

Case1: 1 / 1
Case2: 1 / 2
Case3: -1 / 4
Label: 45 / 256
Otherlabel: 268201436794928 / 320361328125
Biggest: -71542844799237379223056641850683038399677651990786654293842285446351016224553939010

882650681431892067495137019178862799169155069446928707568453465 /



Note: The output for each case should all be on one line. It is split in the final case here for readability.


T <= 10000

0 <= k <= 50

1 < |r| <= 1000

The timelimit per case is ~x5 my Java solution.

hide comments
(Tjandra Satria Gunawan)(曾毅昆): 2012-11-21 15:20:31

@[Retired] Blue.Mary: I do some precomputation O(50^2), after that, it can be solved with only O(k) ;-) I did that in python, but I don't know in java...

[Rampage] Blue.Mary: 2012-11-21 07:54:00

I guess Java solution with time complexity O(k^2 * BigInteger Operation) can't pass?

Edit: Pike/Java is so slow. O(k * BigInteger Operation) per test case almost gets TLE.

Last edit: 2012-11-23 06:25:31
Francky: 2012-11-04 18:26:07

I had a very poor/limited BigNum emulation for INCPOWK, so I had to build my first quite-complete attempt for this problem. It cost my some time, but I'm very happy to had this awesome problem to force me to do the job. Thanks to the author.

Alex Anderson: 2012-10-13 00:58:53

Tanmay, there is a faster/better way to calculate the coefficients, if you still want to use them, though they aren't necessary to solve the problem. (Currently you are recalculating the same values a lot of times)

And using BigInteger is fine, just be effective when you use it.

EDIT: Tanmay, you are actually very close to solving the problem. There's one thing you can easily optimize, then AC.

Last edit: 2012-10-13 01:32:00
Francky: 2012-10-12 19:13:17

@Tanmay : you don't need those coefficients. Try to manage without them.

Tanmay: 2012-10-12 16:11:32

TLE :(
Even after optimizing a LOT.
<spoiler> Mostly because I still don't know how to find binomial coefficients without using BigInteger in Java. </spoiler>

:D: 2012-10-08 06:56:47

Another chapter in my book "Failing with Python 101" :)

I guess I was missing some vital optimization. I wouldn't blame it on the problem though. It was great!

(Tjandra Satria Gunawan)(曾毅昆): 2012-10-08 03:52:39

seems that my BigInt algo in C is very slow :-( I still need 2x this (lower bound) time limit to get Accepted in C.

Last edit: 2012-10-08 04:11:27
Alex Anderson: 2012-10-08 01:01:44

Efficiency is still good, but it wasn't my intention to make things require micro-optimizations so I'll raise the time bounds a bit. Some "random" sampling of submissions that already were done showed correct answers for several that had previously timed out, some were wrong, and some still timed out.

I've raised the time limit by a factor of 2.

I'm not sure how to account for such variance in the runtimes, so I suppose guesswork will have to do.

Last edit: 2012-10-08 01:02:29
Robert Gerbicz: 2012-10-08 01:01:44

Time limit is more than enough. Solved in c in 0.33 sec.

Added by:Alex Anderson
Time limit:1s-5.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem