Fractal Shortest Path

AtCoder

IDpanasonic2020_f

Time2000ms

Memory256MB

Difficulty—

For a non-negative integer $K$, we define a fractal of level $K$ as follows: * A fractal of level $0$ is a grid with just one white square. * When $K > 0$, a fractal of level $K$ is a $3^K \times 3^K$ grid. If we divide this grid into nine $3^{K-1} \times 3^{K-1}$ subgrids: * The central subgrid consists of only black squares. * Each of the other eight subgrids is a fractal of level $K-1$. For example, a fractal of level $2$ is as follows: ![image](https://img.atcoder.jp/panasonic2020/e3a473bc5b6d3ac74c3ab8130213ef09.png) In a fractal of level $30$, let $(r, c)$ denote the square at the $r$\-th row from the top and the $c$\-th column from the left. You are given $Q$ quadruples of integers $(a_i, b_i, c_i, d_i)$. For each quadruple, find the distance from $(a_i, b_i)$ to $(c_i, d_i)$. Here the distance from $(a, b)$ to $(c, d)$ is the minimum integer $n$ that satisfies the following condition: * There exists a sequence of white squares $(x_0, y_0), \ldots, (x_n, y_n)$ satisfying the following conditions: * $(x_0, y_0) = (a, b)$ * $(x_n, y_n) = (c, d)$ * For every $i (0 \leq i \leq n-1)$, $(x_i, y_i)$ and $(x_{i+1}, y_{i+1})$ share a side. ## Constraints * $1 \leq Q \leq 10000$ * $1 \leq a_i, b_i, c_i, d_i \leq 3^{30}$ * $(a_i, b_i) \neq (c_i, d_i)$ * $(a_i, b_i)$ and $(c_i, d_i)$ are white squares. * All values in input are integers. ## Input Input is given from Standard Input in the following format: $Q$ $a_1 \ b_1 \ c_1 \ d_1$ $:$ $a_Q \ b_Q \ c_Q \ d_Q$ [samples]

Samples

Input #1

2
4 2 7 4
9 9 1 9

Output #1

5
8

![image](https://img.atcoder.jp/panasonic2020/b590cee9850abdad4109ab940f9efe5a.png)

API Response (JSON)

{
  "problem": {
    "name": "Fractal Shortest Path",
    "description": {
      "content": "For a non-negative integer $K$, we define a fractal of level $K$ as follows: *   A fractal of level $0$ is a grid with just one white square. *   When $K > 0$, a fractal of level $K$ is a $3^K \\times",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "panasonic2020_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "For a non-negative integer $K$, we define a fractal of level $K$ as follows:\n\n*   A fractal of level $0$ is a grid with just one white square.\n*   When $K > 0$, a fractal of level $K$ is a $3^K \\times...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments