【MX-X1-T1】「KDOI-05」简单的无限网格问题

Luogu

IDLGP10713

Time1000ms

Memory512MB

DifficultyP2

O2优化分类讨论梦熊比赛

小 X 正在参加 KDOI 机器人锦标赛。比赛场地是一个**无限大**的网格，小 X 的机器人初始时位于 $(1,1)$，他需要进行若干次操作，使得机器人移动到 $(n,m)$（$n,m\ge 2$）。第 $i$ 次操作时，小 X 可以指定上、下、左、右中的一个方向和一个正整数 $x_i$，然后让机器人向该方向移动 $x_i$ 步。不幸的是，小 X 的机器人出现了一些 bug，因此，他的操作必须满足一些限制，否则机器人就会立即爆炸： + 对于第 $i$ 次操作，若 $i$ 是奇数，则 $x_i$ 也是奇数；若 $i$ 是偶数，则 $x_i$ 也是偶数。请帮助小 X 计算出使他的机器人到达 $(n,m)$ 的最小操作次数。 ## Input **本题包含多组测试数据。** 输入的第一行包含一个正整数 $T$，表示测试数据组数。对于每组测试数据，输入包含一行两个正整数 $n,m$。 ## Output 对于每组测试数据，输出一行一个整数，表示答案。可以证明，小 X 的机器人一定能在有限步内到达 $(n,m)$。 [samples] ## Background 原题链接：<https://oier.team/problems/X1A>。 ## Note **【样例解释】** 对于第一组数据，可以按如下方式移动： $$(1,1)\to(8,1)\to(8,7)$$ 总共需要 $2$ 次操作。可以证明没有比这更优的操作方案。 **【数据范围】** **本题采用捆绑测试。** | 子任务编号 | 分值 | $n,m\leq$ | 特殊性质 | |:--:|:--:|:--:|:--:| | $1$ | $30$ | $10$ | 无 | | $2$ | $30$ | $10^9$ | $n,m$ 奇偶性相同 | | $3$ | $40$ | $10^9$ | 无 | 对于 $100\%$ 的数据：$1\leq T\leq10^5$，$2\leq n,m\leq10^9$。

Samples

Input #1

3
8 7
999999 1000000
3 3

Output #1

2
2
3

API Response (JSON)

{
  "problem": {
    "name": "【MX-X1-T1】「KDOI-05」简单的无限网格问题",
    "description": {
      "content": "小 X 正在参加 KDOI 机器人锦标赛。 比赛场地是一个**无限大**的网格，小 X 的机器人初始时位于 $(1,1)$，他需要进行若干次操作，使得机器人移动到 $(n,m)$（$n,m\\ge 2$）。 第 $i$ 次操作时，小 X 可以指定上、下、左、右中的一个方向和一个正整数 $x_i$，然后让机器人向该方向移动 $x_i$ 步。 不幸的是，小 X 的机器人出现了一些 bug，因此，他",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10713"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 X 正在参加 KDOI 机器人锦标赛。\n\n比赛场地是一个**无限大**的网格，小 X 的机器人初始时位于 $(1,1)$，他需要进行若干次操作，使得机器人移动到 $(n,m)$（$n,m\\ge 2$）。\n\n第 $i$ 次操作时，小 X 可以指定上、下、左、右中的一个方向和一个正整数 $x_i$，然后让机器人向该方向移动 $x_i$ 步。\n\n不幸的是，小 X 的机器人出现了一些 bug，因此，他...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments