AT_abc353_f [ABC353F] Tile Distance

题目描述

在坐标平面上铺有瓷砖。有两种瓷砖：$1\times1$ 大小的小瓷砖和 $K\times K$ 大小的大瓷砖，铺设规则如下：

• 对于整数对 $(i, j)$，正方形 $\lbrace(x, y)\mid i\leq x\leq i+1\wedge j\leq y\leq j+1\rbrace$ 属于某一个小瓷砖或某一个大瓷砖。
  • 当 $\left\lfloor\dfrac{i}{K}\right\rfloor+\left\lfloor\dfrac{j}{K}\right\rfloor$ 为偶数时，属于小瓷砖。
  • 否则，属于大瓷砖。

注意，瓷砖包含其边界，且不存在两个不同的瓷砖有正面积的公共部分。

例如，当 $K=3$ 时，瓷砖的铺设如下图所示：

高桥君一开始位于坐标平面上的点 $(S_x+0.5, S_y+0.5)$。

高桥君可以任意多次重复以下移动：

• 选择一个方向（上下左右）和一个正整数 $n$，向该方向移动 $n$ 个单位。

每当高桥君经过不同的瓷砖时，他需要支付 $1$ 的通行费。

请你求出高桥君从 $(S_x+0.5, S_y+0.5)$ 到达 $(T_x+0.5, T_y+0.5)$ 所需支付的最小通行费。

输入格式

输入以以下格式从标准输入读入。

$K$ $S_x$ $S_y$ $T_x$ $T_y$

输出格式

输出高桥君需要支付的最小通行费。

输入输出样例 #1

输入 #1

3
7 2
1 6

输出 #1

5

输入输出样例 #2

输入 #2

1
41 42
13 56

输出 #2

42

输入输出样例 #3

输入 #3

100
100 99
199 1

输出 #3

0

输入输出样例 #4

输入 #4

96929423
5105216413055191 10822465733465225
1543712011036057 14412421458305526

输出 #4

79154049

说明/提示

限制条件

• $1\leq K\leq 10^{16}$
• $0\leq S_x\leq 2\times10^{16}$
• $0\leq S_y\leq 2\times10^{16}$
• $0\leq T_x\leq 2\times10^{16}$
• $0\leq T_y\leq 2\times10^{16}$
• 输入均为整数

样例解释 1

例如，可以按如下方式移动，使得通行费为 $5$。

• 向上移动 $3$，支付通行费 $1$。
• 向左移动 $2$，支付通行费 $1$。
• 向上移动 $1$，支付通行费 $1$。
• 向左移动 $4$，支付通行费 $2$。

无法将通行费降到 $4$ 以下，因此输出 5。

样例解释 2

当高桥君以最短距离移动时，无论如何移动，通行费都为 $42$。无法将通行费降到 $41$ 以下，因此输出 42。

样例解释 3

有时也可能不需要支付通行费。

由 ChatGPT 4.1 翻译