Problem J
Limbo: Part 2
Dominick Cobb and Arthur are “extractors" who perform
corporate espionage. Using experimental military technology
that gives them access to shared dream worlds, they infiltrate
their targets’ subconscious to extract valuable information.
Cobb and his entourage are contacted by a mysterious Japanese
syndicate and given a seemingly impossible task: instead of
extracting information, do the opposite – plant a new idea in
the target’s mind.
Cobb just figured out how to calculate the slowness of time
in each dream level, but he is still missing a vital piece of
the plan – the architecture. For this challenging mission he
has hired the brilliant young architect Ariadne to design a
dream space, complete with all the aesthetic and tactile
details. Cobb’s target will be brought into that dream space,
where they will fill it with details from their own
subconscious and memories.
As extractors go into deeper dream levels, the perception of
time slows down. This means subjects will be able to explore
exponentially more space. Since dreams can go infinitely deep
(onwards to Limbo), the architecture of a dream should be
infinite in area. The master layout is denoted by a
two-dimensional grid that starts at row $0$, column $0$, and extends infinitely downwards
and to the right. Ariadne cannot simply draw a map of this
space (since it is infinite), so she must come up with a
program that "generates" the dream space to extend as large as
the team needs to go deeper. She has an infinite number of
building blocks, numbered $0, 1,
2, 3, 4, \dots $, which must be used in that
order.
In dream level $0$
(reality), the dream space consists of the single block
$0$. With each deeper
dream level, the area of the space doubles. To prevent the
dream space from implosion due to growing too narrowly in a
single direction, Ariadne has designed the space to double in
alternating directions, with new blocks
filling in the space sequentially based on the direction of
doubling. For example, the first few levels of the dream map
are depicted as follows:
0 0 1 0 1 0 1 4 6
2 3 2 3 5 7
(Reality) (Level 1) (Level 2) (Level 3)
0 1 4 6 0 1 4 6 16 20 24 28
2 3 5 7 2 3 5 7 17 21 25 29
8 9 10 11 8 9 10 11 18 22 26 30
12 13 14 15 12 13 14 15 19 23 27 31
(Level 4) (Level 5)
Ariadne’s program must be able to generate any part of the map at will. Given only the row and column coordinates for a particular location in the dream space, can you determine the number of the building block that will be used?
Input
The first line of input consists of a single integer
$T$ ($1 \leq T \leq 100$), the number of
test cases.
$T$ lines follow, each of
which is a test case consisting of two space-separated
integers, $R$ and
$C$ ($0 \leq R, C \leq 10^{9}$), specifying
a particular row and column in the dream-space.
Output
For each test case, print, on a separate line, the number of
the building block at coordinates $(R, C)$.
Note: the answer can be large, and may not necessarily fit in a
32-bit integer.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 0 0 1 0 2 4 |
0 2 18 |
