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 iK\right\rfloor+\left\lfloor\dfrac jK\right\rfloor$ 为偶数，则它被包含在一个小瓷砖内。 否则，它被包含在一个大瓷砖内。

瓷砖包含它们的边界，并且没有两个不同的瓷砖有正面积的交集。 例如，当 $K=3$ 时，瓷砖如下图所示铺设： Takahashi 从坐标平面上的点 $(S_x+0.5,S_y+0.5)$ 出发。 他可以重复以下移动任意次：

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

每次他从一个瓷砖跨到另一个瓷砖时，必须支付通行费 $1$。 求 Takahashi 到达点 $(T_x+0.5,T_y+0.5)$ 所需支付的最小通行费。

输入格式

输入从标准输入按以下格式给出： $K$ $S_x$ $S_y$ $T_x$ $T_y$

输出格式

输出 Takahashi 必须支付的最小通行费。

3
7 2
1 6

5

1
41 42
13 56

42

100
100 99
199 1

0

96929423
5105216413055191 10822465733465225
1543712011036057 14412421458305526

79154049

提示

$1\leq K\leq10^{16}$ $0\leq S_x\leq2\times10^{16}$ $0\leq S_y\leq2\times10^{16}$ $0\leq T_x\leq2\times10^{16}$ $0\leq T_y\leq2\times10^{16}$ 所有输入值均为整数。例如，他可以如下移动，支付通行费 $5$。

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

所付通行费不可能是 $4$ 或更少，所以输出 $5$。
当他按最短距离移动时，他将始终支付通行费 $42$。 所付通行费不可能是 $41$ 或更少，所以输出 $42$。
存在一些情况不需要支付任何通行费。

标签: AtCoder|abc353F

来源

AtCoder|abc353F