TopCoder problem "LocateTreasure" used in SRM 427 (Division I Level Two)



Problem Statement

    First of all we define a function dig for all nonnegative integers:

dig(x) := x                          if 0 <= x <= 9
dig(x) := dig(sum of digits of x)    if x >= 10
For example: dig(49) = dig(13) = dig(4) = 4.



Your crew of treasure hunters have recently found a very old map with instructions on how to find the treasure of an old civilization. There is a variable named Gold number, and it is initially assigned a value of 1. You are currently standing at position (0, 0), facing north.



Repeat the following instructions K times:

1. Take dig(Gold number) steps forward, and then turn 90 degrees right.

2. Multiply Gold number by multi.



Each step forward moves you one unit in your current direction. Moving north changes your location by (0, 1), south changes your location by (0, -1), west changes your location by (-1, 0) and east changes your location by (1, 0). After you perform all the instructions, you can start digging. Return the coordinates (X, Y) of your final location as a String in the form "X Y" (quotes for clarity), where X and Y contain no extra leading zeroes.

 

Definition

    
Class:LocateTreasure
Method:location
Parameters:int, int
Returns:String
Method signature:String location(int K, int multi)
(be sure your method is public)
    
 

Constraints

-K will be between 1 and 10^9, inclusive.
-multi will be between 1 and 1000, inclusive.
 

Examples

0)
    
5
2
Returns: "-6 4"
You will go 1 step north, 2 steps east, 4 steps south, 8 steps west and 7 steps north.
1)
    
99
1
Returns: "1 0"
You will do exactly 1 step in every iteration.
2)
    
6
9
Returns: "9 1"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=9984

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13518&pm=9984

Writer:

rasto6sk

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Dynamic Programming, Math