102585: [AtCoder]ABC258 F - Main Street
Description
Score : $500$ points
Problem Statement
The roads in the Kingdom of AtCoder, which lies on the xy-plane, are the lines $x=n$ and $y=n$ for all integers $n$. Among them, the lines $x=Bn$ and $y=Bn$ for all integers $n$ are main roads.
When Takahashi is at $(x,y)$, he can move to $(x,y-1)$, $(x,y+1)$, $(x+1,y)$, or $(x-1,y)$. Each move takes $1$ second along a main road and $K$ seconds otherwise.
Find the minimum number of seconds Takahashi needs to get from $(S_x, S_y)$ to $(G_x, G_y)$.
You will have $T$ test cases to solve.
Constraints
- $1 \le T \le 2 \times 10^5$
- $1 \le B,K \le 10^9$
- $0 \le S_x,S_y,G_x,G_y \le 10^9$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$T$
$\mathrm{testcase}_1$
$\mathrm{testcase}_2$
$\vdots$
$\mathrm{testcase}_T$
Each test case is in the following format:
$B$ $K$ $S_x$ $S_y$ $G_x$ $G_y$
Output
Print $T$ lines. The $i$-th line should contain the answer to the $i$-th test case.
Sample Input 1
4 3 4 2 2 4 4 5 6 2 3 2 3 1 1000000000 0 0 1000000000 1000000000 1000000000 1000000000 500000000 500000000 1000000000 1000000000
Sample Output 1
10 0 2000000000 500000000500000000
For the $1$-st test case, he can go from $(2,2)$ to $(2,3)$ in $4$ seconds, from $(2,3)$ to $(4,3)$ in $2$ seconds, and from $(4,3)$ to $(4,4)$ in $4$ seconds to get from $(2,2)$ to $(4,4)$ in $10$ seconds. It is impossible to get there in less than $10$ seconds, so the answer is $10$.
For the $2$-nd test case, he is already at $(G_x, G_y)$ in the beginning, so the answer is $0$.
Sample Input 2
10 928184439 674654465 203937094 186855052 851783856 805293696 55480262 448852233 823161539 786348805 550018803 322680316 891870741 235679524 32164572 497841190 620600021 96487871 321502816 428964257 499656016 521484999 717623189 824784374 144040837 680268887 76238777 371138006 350230937 78690135 768922620 799628518 403830696 60449731 218880692 88319939 482031503 121412614 472330444 284479575 949635609 427232765 389524418 132987043 656496997 678732442 23028233 488463974 857778764 629964237 714551548 739330018 579247790 874251485 461612428 535402609 555160129 833592114 44418273 287363785
Sample Output 2
177606591118701316 6205925075792263 30320747646118343 84136273267803188 83764071874751489 118960470930399064 2929499649126153 16403238161749820 84995699148879437 71771264361119335
Input
题意翻译
你要在平面直角坐标系中行走，每一步可以上下左右四个方向任意移动 $ 1 $，耗时 $ k $ 秒。特别地，存在若干条快速通道，若该步起点和终点均满足 $ x \equiv 0 \pmod{B} $ 或 $ y \equiv 0 \pmod{B} $，则认为该步是在快速通道上进行，仅需耗时 $ 1 $ 秒。询问从 $ (S_x, S_y) $ 到 $ (G_x, G_y) $ 最少需要多少秒。存在多组数据。Output
分数：500分
问题描述
在xy平面上的王国AtCoder，道路是直线$x=n$和$y=n$，对于所有的整数$n$。其中，对于所有的整数$n$，直线$x=Bn$和$y=Bn$是主干道。
当Takahashi在$(x,y)$时，他可以移动到$(x,y-1)$、$(x,y+1)$、$(x+1,y)$或$(x-1,y)$。沿着主干道的每次移动需要1秒，否则需要$K$秒。
找出Takahashi从$(S_x, S_y)$到$(G_x, G_y)$所需的最短时间。
你将需要解决$T$个测试用例。
约束
- $1 \le T \le 2 \times 10^5$
- $1 \le B,K \le 10^9$
- $0 \le S_x,S_y,G_x,G_y \le 10^9$
- 输入中的所有值都是整数。
输入
输入从标准输入给出，如下所示：
$T$
$\mathrm{testcase}_1$
$\mathrm{testcase}_2$
$\vdots$
$\mathrm{testcase}_T$
每个测试用例的格式如下：
$B$ $K$ $S_x$ $S_y$ $G_x$ $G_y$
输出
打印$T$行。第$i$行应包含第$i$个测试用例的答案。
样例输入1
4 3 4 2 2 4 4 5 6 2 3 2 3 1 1000000000 0 0 1000000000 1000000000 1000000000 1000000000 500000000 500000000 1000000000 1000000000
样例输出1
10 0 2000000000 500000000500000000
对于第1个测试用例，他可以从$(2,2)$移动到$(2,3)$需要4秒，从$(2,3)$移动到$(4,3)$需要2秒，从$(4,3)$移动到$(4,4)$需要4秒，因此从$(2,2)$到$(4,4)$需要10秒。无法在不到10秒的时间内到达那里，所以答案是10秒。
对于第2个测试用例，他一开始就处于$(G_x, G_y)$，所以答案是0。
样例输入2
10 928184439 674654465 203937094 186855052 851783856 805293696 55480262 448852233 823161539 786348805 550018803 322680316 891870741 235679524 32164572 497841190 620600021 96487871 321502816 428964257 499656016 521484999 717623189 824784374 144040837 680268887 76238777 371138006 350230937 78690135 768922620 799628518 403830696 60449731 218880692 88319939 482031503 121412614 472330444 284479575 949635609 427232765 389524418 132987043 656496997 678732442 23028233 488463974 857778764 629964237 714551548 739330018 579247790 874251485 461612428 535402609 555160129 833592114 44418273 287363785
样例输出2
177606591118701316 6205925075792263 30320747646118343 84136273267803188 83764071874751489 118960470930399064 2929499649126153 16403238161749820 84995699148879437 71771264361119335