Quadrants
Time limit2sMemory limit128 MB
Convert a quadrant-encoded grid cell of up to 50 digits into coordinates, shift it by given x and y offsets, and print the resulting quadrant code or -1 if it moves off the grid.
- Level
Medium5 of 10
- Topics
- Math, Implementation, Simulation
- Solved
- No attempts yet
Problem
A coordinate plane is divided into four quadrants: 1 is the upper right, 2 is the upper left, 3 is the lower left, and 4 is the lower right. Each quadrant can be divided again by the same rule, and the number of the smaller piece is formed by appending the inner quadrant number to the outer one. For instance, quadrant 1 inside quadrant 1 is 11, quadrant 2 inside quadrant 3 is 32, and quadrant 1 inside quadrant 4 inside quadrant 3 is 341.
If the number has length d, the plane is divided into a 2^d by 2^d grid, and the number identifies one piece of that grid. Given a quadrant piece, move it x cells horizontally and y cells vertically, then find the number of the piece where it lands. If the moved piece lies outside the whole divided plane, that piece does not exist.
Write a program that prints the quadrant number after the move.
Input
The first line contains an integer d, the number of digits in the quadrant piece number, and the quadrant piece number itself. 1 <= d <= 50.
The second line contains two integers x and y. |x|, |y| <= 250. A positive x moves the piece to the right, and a negative x moves it to the left, by |x| cells. A positive y moves the piece upward, and a negative y moves it downward, by |y| cells.
Output
Print the number of the quadrant piece where it lands. If the moved piece does not exist, print -1.