[Note to plugin users: This problem statement contains images and superscripts. If you do not see the images, or
if 2^{k} is displayed the same as 2k, then please view the problem in the applet.]
A Hilbert curve is a path that traces through all the points in a twodimensional square grid
in such a way that each step in the path moves between neighbors in the grid. Hilbert curves
are sometimes used in image processing because they exhibit greater locality than
other common methods of linearizing a twodimensional image, such as rowbyrow (even
than the boustrophedonic variations of rowbyrow that alternate between lefttoright
and righttoleft).
A rankk Hilbert curve is a path through a 2^{k}by2^{k} grid.
A rank1 Hilbert curve is a simple Ushape through a 2by2 grid, as shown below.
The blue point indicates the first point in the path and the red point indicates the
last point in the path. For k > 1, a rankk Hilbert curve is
composed of four rank(k1) Hilbert curves, shown below as dotted lines.
Notice how the curve is organized in quadrants, first the upper left, then
the lower left, then the lower right, and finally the upper right. (The cross in the
background is not part of the curve; it merely highlights the quadrants.)
Notice also
how some of the rank(k1) curves are flipped and rotated compared to the
orientation of the rankk curve. The blue and red points indicate
where each rank(k1) curve begins and ends, respectively. The overall rankk
curve begins at the first point of the upper left rank(k1) curve and
ends at the last point of the upper right rank(k1) curve. Here is
a complete picture of a rank3 Hilbert curve.
You will be given a value k and coordinates x and y in a
2^{k}by2^{k} grid. Coordinates range from 1 to 2^{k} inclusive,
with the upper left corner at coordinates (1,1). Assuming the points are traversed
in the order specified by a rankk Hilbert curve, determine how many steps it
takes to reach the point at coordinates (x,y). For example,
it takes 0 steps to reach the upper left corner at coordinates (1,1) and 4^{k}1
steps to reach the upper right corner at coordinates (2^{k},1).
