CUBEND - Suffix Of Cube

no tags 

Given any string of decimal digits, ending in 1, 3, 7 or 9,  there is always a decimal
number, which when cubed has a decimal expansion ending in the original given digit
string. The number need never have more digits than the given digit string. 
Write a program, which takes as input a string of decimal digits ending in 1, 3, 7 or 9
and finds a number of at most the same number of digits, which when cubed, ends in
the given digit string.


The input begins with a line containing only the count of problem instances, nProb, as a
decimal integer, 1 <= nProb <= 100.  This is followed by nProb lines, each of which
contains a string of between 1 and 10 decimal digits ending in 1, 3, 7 or 9.


For each problem instance, there should be one line of output consisting of the number,
which when cubed, ends in the given digit string. The number should be output as a
decimal integer with no leading spaces and no leading zeroes. 

If there are many answers, the minimum should be chosen.


9876543213 Output: 947

hide comments
Problem Solver: 2011-06-27 00:23:34

That's a crap :( C++ solution overflows. Good we have python.

Piotr KÄ…kol: 2011-04-30 23:24:49

Is unsigned long long int enough?
Because I get TLE after I optimized my algorithm to be pessimistically O(10*x) where x is the length of the string and it seems to me quite fast.

Edit: It seems that even long double is not enough as 7782948457**2=60574286684318680848. :-/

Last edit: 2011-05-01 12:18:14
:D: 2011-04-20 11:25:55

I don't know if such data case occurs, but in case of input like "0001" simply print "1". That is, you can assume that there are infinitely many leading 0's in the cubes result.

Last edit: 2011-04-20 11:37:25

Added by:Bống
Time limit:0.319s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)