cho.shZ
Given N and coordinates (r,c) in a 2^N x 2^N grid, compute the visit order index of that cell under recursive Z-order (Morton order) traversal.
Easy3Divide and conquerRecursionBit manipulationInterviewNo attempts yetTime limit0.5sMemory limit512 MBProblem
A square array of size 2^N x 2^N is visited in Z-order. In a 2 x 2 array, the cells are visited in this order: upper-left, upper-right, lower-left, lower-right. This order forms a Z shape.
When N > 1, divide the array into four subarrays of size 2^(N-1) x 2^(N-1), then visit those subarrays recursively in the same order: upper-left, upper-right, lower-left, lower-right.
The following figure shows the visit order for an array of size 2^2 x 2^2.
Given N, r, and c, write a program that outputs when the cell at row r and column c is visited.
The following figure shows the visit order when N = 3.
Input
The first line contains three integers N, r, and c.
Output
Print the visit order of the cell at row r and column c.
Constraints
1 <= N <= 150 <= r, c < 2^N