103535: [Atcoder]ABC353 F - Tile Distance

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score: $550$ points

Problem Statement

Tiles are laid out on a coordinate plane. There are two types of tiles: small tiles of size $1\times1$ and large tiles of size $K\times K$, laid out according to the following rules:

  • For each pair of integers $(i,j)$, the square $\lbrace(x,y)\mid i\leq x\leq i+1\wedge j\leq y\leq j+1\rbrace$ is contained within either one small tile or one large tile.
    • If $\left\lfloor\dfrac iK\right\rfloor+\left\lfloor\dfrac jK\right\rfloor$ is even, it is contained within a small tile.
    • Otherwise, it is contained within a large tile.

Tiles include their boundaries, and no two different tiles have a positive area of intersection.

For example, when $K=3$, tiles are laid out as follows:

Takahashi starts at the point $(S_x+0.5,S_y+0.5)$ on the coordinate plane.

He can repeat the following movement any number of times:

  • Choose a direction (up, down, left, or right) and a positive integer $n$. Move $n$ units in that direction.

Each time he crosses from one tile to another, he must pay a toll of $1$.

Determine the minimum toll Takahashi must pay to reach the point $(T_x+0.5,T_y+0.5)$.

Constraints

  • $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}$
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the minimum toll Takahashi must pay.


Sample Input 1

3
7 2
1 6

Sample Output 1

5

For example, he can move as follows, paying a toll of $5$.

  • Move up by $3$. Pay a toll of $1$.
  • Move left by $2$. Pay a toll of $1$.
  • Move up by $1$. Pay a toll of $1$.
  • Move left by $4$. Pay a toll of $2$.

The toll paid cannot be $4$ or less, so print 5.


Sample Input 2

1
41 42
13 56

Sample Output 2

42

When he moves the shortest distance, he will always pay a toll of $42$.

The toll paid cannot be $41$ or less, so print 42.


Sample Input 3

100
100 99
199 1

Sample Output 3

0

There are cases where no toll needs to be paid.


Sample Input 4

96929423
5105216413055191 10822465733465225
1543712011036057 14412421458305526

Sample Output 4

79154049

Output

得分: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$包含在一个小瓷砖或一个大瓷砖内:
    • 如果$\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

加入题单

上一题 下一题 算法标签: