PONY6  Toward Infinity
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.
Input
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.
Output
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.
Example
Input: 6 Case1: 0 2 Case2: 0 3 Case3: 0 3 Label: 2 9 Otherlabel: 12 16 Biggest: 50 555 Output: Case1: 1 / 1 Case2: 1 / 2 Case3: 1 / 4 Label: 45 / 256 Otherlabel: 268201436794928 / 320361328125 Biggest: 71542844799237379223056641850683038399677651990786654293842285446351016224553939010Note: The output for each case should all be on one line. It is split in the final case here for readability.882650681431892067495137019178862799169155069446928707568453465 /
7086055907083154841158073677533359179964732523333455695465110902606507148230087594593
20274728690683789654784801111318621847552
Bounds
T <= 10000
0 <= k <= 50
1 < r <= 1000
The timelimit per case is ~x5 my Java solution.
hide comments
(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20121121 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:
20121121 07:54:00
I guess Java solution with time complexity O(k^2 * BigInteger Operation) can't pass?


Francky:
20121104 18:26:07
I had a very poor/limited BigNum emulation for INCPOWK, so I had to build my first quitecomplete 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:
20121013 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)


Francky:
20121012 19:13:17
@Tanmay : you don't need those coefficients. Try to manage without them. 

Tanmay:
20121012 16:11:32
TLE :(


:D:
20121008 06:56:47
Another chapter in my book "Failing with Python 101" :)


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20121008 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: 20121008 04:11:27 

Alex Anderson:
20121008 01:01:44
Efficiency is still good, but it wasn't my intention to make things require microoptimizations 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.


Robert Gerbicz:
20121008 01:01:44
Time limit is more than enough. Solved in c in 0.33 sec. 
Added by:  Alex Anderson 
Date:  20121006 
Time limit:  1s5.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own Problem 