← 返回题目列表

AtCoder · abc353_f

I. 平铺距离

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

分数: 550 点

问题陈述

图块布置在坐标平面上。有两种类型的瓷砖: 小尺寸瓷砖 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 包含在一个小块或一个大块内。
    • If \left\lfloor\dfrac iK\right\rfloor+\left\lfloor\dfrac jK\right\rfloor 是均匀的,它包含在一个小瓷砖内。
    • 否则,它包含在一个大图块内。

图块包括其边界,并且没有两个不同的图块具有正的相交面积。

例如,当 K=3,图块的布局如下:

高桥从该点开始 坐标平面上的 (S_x+0.5,S_y+0.5) 。

他可以重复以下动作任意次数:

  • 选择一个方向(上、下、左或右)和一个正整数 n。移动 n 单位在该方向。

每次他从一个格子穿越到另一个格子时,他必须支付通行费 1.

确定高桥必须支付的最低通行费才能到达该点 (T_x+0.5,T_y+0.5).

约束

  • 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}
  • 所有输入值均为整数。

输入

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

K
S_x S_y
T_x T_y

输出

打印高桥必须支付的最低通行费。


示例输入 1

3
7 2
1 6

示例输出 1

5

例如,他可以按如下方式移动,支付通行费 5.

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

所支付的通行费不能 4 或更少,因此打印 5.


示例输入 2

1
41 42
13 56

示例输出 2

42

当他移动最短距离时,他总是会支付 42.

所支付的通行费不能 41 或更少,因此打印 42.


示例输入 3

100
100 99
199 1

示例输出 3

0

有些情况下不需要支付通行费。


示例输入 4

96929423
5105216413055191 10822465733465225
1543712011036057 14412421458305526

示例输出 4

79154049