← 返回题目列表

AtCoder · abc382_g

G. 平铺距离 3

中文机器翻译题面 查看原题

分数: 575 点

问题陈述

瓷砖的布局覆盖二维坐标平面。

每个图块都是一个矩形,并且对于每个整数三元组 (i, j, k) 满意 0 \leq k < K,按照以下规则放置相应的图块:

  • 当 i 和 j 具有相同的奇偶性(均为偶数或均为奇数),对应的图块 (i, j, k) 覆盖的区域 iK \leq x \leq (i + 1)K 和 jK + k \leq y \leq jK + k + 1.
  • 当 i 和 j 具有不同的奇偶性,对应的图块 (i, j, k) 覆盖的区域 iK + k \leq x \leq iK + k + 1 和 jK \leq y \leq (j + 1)K.

两块瓷砖是 相邻 当它们的边具有正长度的公共段时。

从包含该点的图块开始 (S_x + 0.5, S_y + 0.5),找到需要移动到相邻图块才能到达包含该点的图块的最少次数 (T_x + 0.5, T_y + 0.5).

有 T 测试用例;解决它们中的每一个。

约束

  • 1 \leq T \leq 10^4
  • 2 \leq K \leq 10^{16}
  • -10^{16} \leq S_x, S_y, T_x, T_y \leq 10^{16}
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

T
\text{case}_1
\vdots
\text{case}_T

每个案例均按以下格式给出:

K S_x S_y T_x T_y

输出

打印 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。


示例输入 1

3
3 -2 1 4 -1
4 8 8 0 2
5 -1000000000000 -1000000000000 1000000000000 1000000000000

示例输出 1

4
4
800000000000

让我们解释一下第一个测试用例。

让 (i, j, k) 表示对应于整数三元组的图块 (i, j, k).

(-1.5, 1.5) 包含在图块中 (-1, 0, 1),和 (4.5, -0.5) 包含在图块中 (1, -1, 2).

例如,通过从图块移动 (-1, 0, 1) to (-1, 0, 2) to (0, 0, 2) to (1, 0, 0) to (1, -1, 2),您可以到达瓷砖 (1, -1, 2) 四次移动到相邻的图块。