← 返回题目列表

AtCoder · arc018_3

C. 更换座位

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

注意:此问题已被标记为有缺陷。在练习过去的问题时,我们建议您优先考虑其他问题。

問題文

在我的学校,每个班的学生人数都非常多。 1,000,000 甚至还有由人组成的班级。
我的班级也不例外。垂直 N 线,水平 M 桌子排列成矩形行, N \times M 每个学生都有自己的桌子。
我校防灾意识较高,一旦发生紧急情况,教室后墙可以剥落,人员可以从那里疏散。
最近,政策发生了变化,避难时最好是能够躲避成绩好的人。所以,在我的班级里,成绩好的学生不得不换座位,坐在教室后面靠墙的地方。 具体来说,教室第一排 0 行,最左边的列 0 作为列 i 行第 j 指该排的座位。 (i, j) ,坐在那里的人换座位后的分数 G[i][j] 然后有 2 一个座位 对于 (a, b), (c, d) 无论 a \gt c 如果 b, d 的值如何 这意味着要更换座位,以便 G[a][b] \geq G[c][d] 始终成立。
学生可以移动到任意座位,但更换座位后, 2 同一座位上不得有超过1人,且不得有空座位。当然,通过添加新桌子或拆除它们, N 行 M 也不允许扰乱行的形状。
如果能换座位就好了,但遗憾的是学生人数非常多,所以我想尽量减少每个学生因换座位而行驶的总距离。此时,学生所走过的距离就是学生移动前后座位位置之间的曼哈顿距离。换句话说 如果移动到 (a, b) 假设一直下雨,直到 (c, d) ,则移动的距离为 |a - c| + |b - d| 。
由于我给出了换座前坐在每个座位上的学生的成绩,因此我想找到学生所行驶的总距离的最小值。


入力

输入是按以下格式从标准输入给出的。

 N   M 
 x_0   a   p 
  • 1 行是一个整数,表示教室中的行数和列数。 N , M ( 1 ≦ N, M ≦ 1,000 ) 用空格分隔。
  • 2 行包含生成每个座位上学生的表现数据的随机数种子。 x_0 ( 0 ≦ x_0 ≦ 10^9 ), a ( 0 ≦ a ≦ 10^9 ), p ( N \times M ≦ p ≦ 10^9 , p 始终是质数) 用空格分隔。 由于座位数量较多,因此以上述三个变量为种子,生成换座前每个座位上的学生成绩。 关于 i \geq 1 由递推公式 x_i = (x_{i-1} + a) mod p 给出的序列 考虑 x 。 (i, j) 换座前就座的学生成绩为 x_{i \times m + j} 。

出力

输出一排换座位时每个学生所行驶总距离的最小值。
请在输出末尾添加换行符。

入力例1

2 3
1 2 59

出力例1

0
换座前各座位上的学生成绩如下。
1  3  5
7  9 11
满足条件,因为我后面(屏幕下方)任何座位上都没有成绩比我差的人。因此,无需更换座位。

入力例2

2 3
6 55 59

出力例2

2
换座前各座位上的学生成绩如下。
 6  2 57
53 49 45
(0, 2) 和 在 (1, 2) 应该只是交换座位。在一起 由于变化为 1 ,因此行驶的总距离为 2 。

入力例3

4 5
15 25 79

出力例3

26
换座前各座位上的学生成绩如下。
15 40 65 11 36
61  7 32 57  3
28 53 78 24 49
74 20 45 70 16
以下是满足条件的座位变更示例。
15  7 16 11  3
28 20 32 24 36
53 40 45 57 49
74 61 65 70 78