P8730 [Lanqiao Cup 2020 National ABC] Peano Curve Distance
Description
A Peano curve is a curve on a plane.
The figure below shows the order-$1$ Peano curve. It starts from the lower-left corner, passes through every cell in a $3 \times 3$ grid, and finally reaches the upper-right corner.
The figure below shows the order-$2$ Peano curve. It passes through every cell in a $3^{2} \times 3^{2}$ grid. It is obtained by replacing each cell of the order-$1$ curve with an order-$1$ curve.
The figure below shows the order-$3$ Peano curve. It passes through every cell in a $3^{3} \times 3^{3}$ grid. It is obtained by replacing each cell of the order-$2$ curve with an order-$1$ curve. (Note: in the picture below, the last column is missing one edge due to a drawing error.)
A Peano curve always starts from the lower-left corner and finally reaches the upper-right corner.
We place these cells in a coordinate system. For an order-$k$ Peano curve, the lower-left corner is $(0,0)$, the upper-right corner is $\left(3^{k}-1,3^{k}-1\right)$, the lower-right corner is $\left(3^{k}-1,0\right)$, and the upper-left corner is $\left(0,3^{k}-1\right)$.
Given the coordinates of two points on an order-$k$ Peano curve, what is the distance between these two points if you walk along the Peano curve?
Input Format
The first line contains a positive integer $k$, the order of the Peano curve.
The second line contains two integers $x_{1}, y_{1}$, representing the coordinates of the first point.
The third line contains two integers $x_{2}, y_{2}$, representing the coordinates of the second point.
Output Format
Output one integer, representing the distance between the given two points.
Explanation/Hint
For $30\%$ of the test cases, $0 \leq k \leq 10$.
For $50\%$ of the test cases, $0 \leq k \leq 20$.
For all test cases, $0 \leq k \leq 100$, $0 \leq x_{1}, y_{1}, x_{2}, y_{2} < 3^{k}$, and $x_{1}, y_{1}, x_{2}, y_{2} \leq 10^{18}$. The testdata guarantees that the answer does not exceed $10^{18}$.
Lanqiao Cup 2020 National Finals, Group A Problem F (Group B Problem F, Group C Problem H).
Translated by ChatGPT 5