PowerOfThree
SRM 604 · 2013-12-22 · by cgy4ever
SRM 604 · 2013-12-22 · by cgy4ever · Math
Problem Statement
Problem Statement
Fox Ciel has a robot.
The robot is located on an infinite plane.
At the beginning, the robot starts at the coordinates (0, 0).
The robot can then make several steps.
The steps are numbered starting from 0.
In each step, Ciel must choose one of four directions for the robot: left (x coordinate decreases), right (x coordinate increases), up (y coordinate increases), or down (y coordinate decreases). In step k, the robot will move 3^k units in the chosen direction. It is not allowed to skip a step.
You are givenint s x and y.
Return "Possible" (quotes for clarity) if it is possible that the robot reaches the point (x,y) after some (possibly zero) steps.
Otherwise, return "Impossible".
In each step, Ciel must choose one of four directions for the robot: left (x coordinate decreases), right (x coordinate increases), up (y coordinate increases), or down (y coordinate decreases). In step k, the robot will move 3^k units in the chosen direction. It is not allowed to skip a step.
You are given
Constraints
- x will be between -1,000,000,000 and 1,000,000,000, inclusive.
- y will be between -1,000,000,000 and 1,000,000,000, inclusive.
Examples
0)
1 3 Returns: "Possible"
In step 0 Ciel will send the robot right to (1,0). In step 1 she will send it up to (1,3).
1)
0 2 Returns: "Possible"
The robot will move from (0,0) down to (0,-1) and then up to (0,2).
2)
1 9 Returns: "Impossible"
Note that it is not allowed to move the robot right in step 0, skip step 1, and then move the robot up in step 2.
3)
3 0 Returns: "Impossible"
4)
1 1 Returns: "Impossible"
Submissions are judged against all 151 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PowerOfThree with a public method string ableToGet(int x, int y) · 151 test cases · 2 s / 256 MB per case