← 返回题目列表

Codeforces · 2035/A

A. 滑动

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

有 $$$n$$$ 行 $$$m$$$ 人。令第$$$r$$$行和第$$$c$$$列中的位置由$$$(r, c)$$$表示。按行优先顺序从 $$$1$$$ 开始对每个人进行编号,即编号为 $$$(r-1)\cdot m+c$$$ 的人最初位于 $$$(r,c)$$$。

$$$(r, c)$$$ 的人决定离开。为了填补这个空白,让离开的人编号为$$$i$$$。每个编号为 $$$j>i$$$ 的人都会移动到编号为 $$$j-1$$$ 的人最初所在的位置。下图说明了 $$$n=2$$$、$$$m=3$$$、$$$r=1$$$ 和 $$$c=2$$$ 的情况。

计算每个人运动的曼哈顿距离之和。如果一个人最初位于 $$$(r_0, c_0)$$$,然后移动到 $$$(r_1, c_1)$$$,则曼哈顿距离为 $$$|r_0-r_1|+|c_0-c_1|$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。

每个测试用例的唯一行包含 $$$4$$$ 整数 $$$n$$$、$$$m$$$、$$$r$$$ 和 $$$c$$$ ($$$1\le r\le n\le 10^6$$$、$$$1 \le c \le m \le 10^6$$$),其中 $$$n$$$ 是rows,$$$m$$$ 是列数,$$$(r,c)$$$ 是离开的人最初所在的位置。

输出

对于每个测试用例,输出一个表示曼哈顿距离总和的整数。

示例

输入 #1

4
2 3 1 2
2 2 2 1
1 1 1 1
1000000 1000000 1 1

输出 #1

6
1
0
1999998000000

注意

对于第一个测试用例,编号$$$2$$$的人离开,编号$$$3$$$、$$$4$$$、$$$5$$$和$$$6$$$的人的移动距离分别为$$$1$$$、$$$3$$$、$$$1$$$和$$$1$$$。所以答案是$$$1+3+1+1=6$$$。

对于第二个测试用例,编号为 $$$3$$$ 的人离开,编号为 $$$4$$$ 的人移动。答案是$$$1$$$。