2358: 「NOIP2020」移球游戏
题目描述
小 C 正在玩一个移球游戏,他面前有n+1 根柱子,柱子从 1∼n+1 编号,其中 11 号柱子、22 号柱子、……、n 号柱子上各有 m 个球,它们自底向上放置在柱子上, n+1 号柱子上初始时没有球。这n×m 个球共有 n 种颜色,每种颜色的球各m 个。
初始时一根柱子上的球可能是五颜六色的,而小 C 的任务是将所有同种颜色的球移到同一根柱子上,这是唯一的目标,而每种颜色的球最后放置在哪根柱子则没有限制。
小 C 可以通过若干次操作完成这个目标,一次操作能将一个球从一根柱子移到另一根柱子上。更具体地,将x 号柱子上的球移动到y 号柱子上的要求为:
- x 号柱子上至少有一个球;
- y 号柱子上至多有m−1 个球;
- 只能将 x 号柱子最上方的球移到y 号柱子的最上方。
小 C 的目标并不难完成,因此他决定给自己加加难度:在完成目标的基础上,使用的操作次数不能超过 820000。换句话说,小 C 需要使用至多820000 次操作完成目标。
小 C 被难住了,但他相信难不倒你,请你给出一个操作方案完成小 C 的目标。合法的方案可能有多种,你只需要给出任意一种,题目保证一定存在一个合法方案。
输入
第一行两个用空格分隔的整数 n,m。分别表示球的颜色数、每种颜色球的个数。
接下来 n 行每行 m 个用单个空格分隔的整数,第 i 行的整数按自底向上的顺序依次给出了 i 号柱子上的球的颜色。
输出
接下来 k 行每行你应输出两个用单个空格分隔的正整数 x,y,表示这次操作将 x 号柱子最上方的球移动到y 号柱子最上方。你应保证 1≤x,y≤n+1 且x≠
y。
样例输入 复制
2 3
1 1 2
2 1 2
样例输出 复制
6
1 3
2 3
2 3
3 1
3 2
3 2
提示
【样例 #1 解释】
柱子中的内容为:按自底向上的顺序依次给出柱子上每个球的颜色。
操作 |
1 号柱子 |
2 号柱子 |
3 号柱子 |
初始 |
1 1 2 |
2 1 2 |
|
1 3 |
1 1 |
2 1 2 |
2 |
2 3 |
1 1 |
2 1 |
2 2 |
2 3 |
1 1 |
2 |
2 2 1 |
3 1 |
1 1 1 |
2 |
2 2 |
3 2 |
1 1 1 |
2 2 |
2 |
3 2 |
1 1 1 |
2 2 2 |
【数据范围】
测试点编号 |
n≤ |
m≤ |
1∼2 |
2 |
20 |
3∼5 |
10 |
20 |
6∼8 |
50 |
85 |
9∼14 |
50 |
300 |
15∼20 |
50 |
400 |
对于所有测试点,保证 2≤n≤50, 2≤m≤400。