LocateTreasure

SRM 427 · 2008-11-25 · by rasto6sk

SRM 427 · 2008-11-25 · by rasto6sk · Dynamic Programming, Math

Show categories

Class Name: LocateTreasure

Return Type: String

Method Name: location

Arg Types: (int, int)

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.

Constraints

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

Examples

5
2
Returns: "-6 4"

You will go 1 step north, 2 steps east, 4 steps south, 8 steps west and 7 steps north.

99
1
Returns: "1 0"

You will do exactly 1 step in every iteration.

5226
4
Returns: "10 -2"

6
9
Returns: "9 1"

1000000000
2
Returns: "-6 -3"

Submissions are judged against all 113 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class LocateTreasure with a public method string location(int K, int multi) · 113 test cases · 2 s / 256 MB per case