注意:此问题已被标记为有缺陷。在练习过去的问题时,我们建议您优先考虑其他问题。
問題文
我的班级也不例外。垂直 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