/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 550 点
問題文
座標平面上にタイルが敷き詰められています。 1\times1 の大きさの小タイルと K\times K の大きさの大タイルの 2 種類があり、次の規則に従って敷き詰められています。
- 整数の組 (i,j) に対し、正方形 \lbrace(x,y)\mid i\leq x\leq i+1\wedge j\leq y\leq j+1\rbrace は 1 つの小タイルもしくは 1 つの大タイルに含まれる。
- \left\lfloor\dfrac iK\right\rfloor+\left\lfloor\dfrac jK\right\rfloor が偶数のとき、小タイルに含まれる。
- そうでないとき、大タイルに含まれる。
ただし、タイルは境界を含むものとし、共通部分が正の面積をもつような 2 つの異なるタイルは存在しないとします。
例えば、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
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