4604 - NOIP 2020 提高 第三题 移球游戏（ball）

通过次数

0

提交次数

0

时间限制 : 1 秒
内存限制 : 512 MB

小 C 正在玩一个移球游戏，他面前有 n + 1 根柱子，柱子从 1 ∼ n + 1 编号，其中 1 号柱子、2 号柱子、· · ·、n 号柱子上各有 m 个球，它们自底向上放置在柱子上，n + 1 号柱子上初始时没有球。这 n × m 个球共有 n 种颜色，每种颜色的球各 m 个。 初始时一根柱子上的球可能是五颜六色的，而小 C 的任务是将所有同种颜色的 球移到同一根柱子上，这是唯一的目标，而每种颜色的球最后放置在哪根柱子则没有 限制。 小 C 可以通过若干次操作完成这个目标，一次操作能将一个球从一根柱子移到另 一根柱子上。更具体地，将 x 号柱子上的球移动到 y 号柱子上的要求为：

  1. x 号柱子上至少有一个球；
  2. y 号柱子上至多有 m − 1 个球；
  3. 只能将 x 号柱子最上方的球移到 y 号柱子的最上方。 小 C 的目标并不难完成，因此他决定给自己加加难度：在完成目标的基础上，使用 的操作次数不能超过 820000。换句话说，小 C 需要使用至多 820000 次操作完成目标。 小 C 被难住了，但他相信难不倒你，请你给出一个操作方案完成小 C 的目标。合 法的方案可能有多种，你只需要给出任意一种，题目保证一定存在一个合法方案。

输入

第一行两个用空格分隔的整数 n，m。分别表示球的颜色数、每种颜色球的个数。 接下来 n 行每行 m 个用单个空格分隔的整数，第 i 行的整数按自底向上的顺序依 次给出了 i 号柱子上的球的颜色。

输出

本题采用自定义校验器（special judge）评测。 你的输出的第一行应该仅包含单个整数 k，表示你的方案的操作次数。你应保证 0 ≤ k ≤ 820000。 接下来 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

输入

2 20
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 2 1

输出

39
1 3
1 3
1 3
2 3
2 1
2 1
2 3
2 1
3 2
3 2
3 2
3 2
3 2
1 3
1 3
1 3
2 1
2 1
2 1
1 2
1 2
1 3
1 2
1 3
1 3
1 3
1 3
1 3
1 3
1 3
1 3
1 3
1 3
1 3
1 3
1 3
1 3
1 3
1 3

输入

10 20
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 4 7 2 9
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 10 3 4 1 5
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 9 7 7 4 6
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 10 3 7 6 5
7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 2 3 1 2 5
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 6 9 10 8 9
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 2 1 4 3 6
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 2 8 9 8 5
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 8 4 1 6 5
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 8 7 3 1 10

输出

1273
1 11
10 1
11 10
1 11
10 1
6 11
6 11
6 11
6 11
6 11
6 11
6 11
6 11
6 11
6 11
6 11
6 11
6 11
6 11
6 11
6 11
1 10
1 11
1 11
1 11
1 6
1 6
1 6
1 6
1 6
1 6
1 6
1 6
1 6
1 6
1 6
1 6
1 6
1 6
1 6
1 6
11 1
11 1
11 1
11 1
11 1
11 1
11 1
11 1
11 1
11 1
11 1
11 1
11 1
11 1
11 1
11 1
11 1
11 1
11 1
6 11
6 11
6 11
6 11
6 11
6 11
6 11
6 11
6 11
6 11
6 11
6 11
6 11
6 11
6 11
6 11
1 6
1 6
1 6
1 6
1 6
1 6
1 6
1 6
1 6
1 6
1 6
1 6
1 6
1 6
1 6
1 6
4 11
6 1
6 1
6 1
6 1
6 1
6 1
6 1
6 1
6 1
6 1
6 1
6 1
6 1
6 4
11 6
4 11
6 4
2 11
4 6
4 6
4 6
4 6
4 2
11 4
2 11
4 2
9 11
2 4
2 4
2 4
2 4
2 9
11 2
9 11
2 9
3 2
3 2
3 2
3 2
3 6
3 6
3 6
3 6
3 6
3 6
3 6
3 6
3 6
3 1
3 1
3 1
3 1
3 6
3 4
3 2
8 3
10 8
3 10
8 3
10 8
6 3
6 3
6 3
6 3
6 3
6 3
6 3
6 3
6 3
6 3
6 3
6 3
6 3
6 3
6 3
6 3
8 10
8 3
8 6
8 3
8 3
8 6
8 6
8 6
8 6
8 6
8 6
8 6
8 6
8 6
8 6
8 6
8 6
8 6
8 6
8 6
3 8
3 8
3 8
3 8
3 8
3 8
3 8
3 8
3 8
3 8
3 8
3 8
3 8
3 8
3 8
3 8
3 8
3 8
3 8
6 3
6 3
6 3
6 3
6 3
6 3
6 3
6 3
6 3
6 3
6 3
6 3
6 3
6 3
6 3
6 3
8 6
8 6
8 6
8 6
8 6
8 6
8 6
8 6
8 6
8 6
8 6
8 6
8 6
8 6
8 6
8 6
1 3
1 3
6 1
6 8
6 8
6 8
6 8
6 8
6 1
3 6
3 6
1 3
1 3
6 1
6 1
9 3
1 6
1 6
1 6
1 6
1 9
3 1
9 3
1 9
2 1
2 1
2 1
2 1
2 6
2 8
2 8
2 8
2 8
2 8
2 8
2 8
2 8
2 8
2 8
2 8
2 8
2 6
2 6
2 1
7 2
10 2
10 2
10 2
10 2
10 7
2 10
2 10
2 10
2 10
2 10
7 2
10 7
8 2
8 2
8 2
8 2
8 2
8 2
8 2
8 2
8 2
8 2
8 2
8 2
8 2
8 2
8 2
7 10
7 2
7 2
7 2
7 2
7 8
7 8
7 8
7 8
7 8
7 8
7 8
7 8
7 8
7 8
7 8
7 8
7 8
7 8
7 8
2 7
2 7
2 7
2 7
2 7
2 7
2 7
2 7
2 7
2 7
2 7
2 7
2 7
2 7
2 7
2 7
2 7
2 7
2 7
8 2
8 2
8 2
8 2
8 2
8 2
8 2
8 2
8 2
8 2
8 2
8 2
8 2
8 2
8 2
7 8
7 8
7 8
7 8
7 8
7 8
7 8
7 8
7 8
7 8
7 8
7 8
7 8
7 8
7 8
9 2
9 2
9 2
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 9
8 9
8 9
2 8
2 8
2 8
9 2
9 2
9 2
8 9
8 9
8 9
6 2
9 8
9 8
9 8
9 8
9 6
2 9
6 2
9 6
1 9
1 9
1 9
1 9
1 8
1 8
1 8
1 8
1 8
1 8
1 8
1 8
1 8
1 8
1 8
1 8
1 8
1 8
1 8
1 9
5 1
10 1
10 1
10 1
10 1
10 5
1 10
1 10
1 10
1 10
1 10
5 1
10 5
9 1
9 1
9 1
9 1
9 1
9 1
9 1
9 1
9 1
9 1
9 1
9 1
9 1
9 1
9 1
5 10
5 1
5 1
5 1
5 1
5 9
5 9
5 9
5 9
5 9
5 9
5 9
5 9
5 9
5 9
5 9
5 9
5 9
5 9
5 9
1 5
1 5
1 5
1 5
1 5
1 5
1 5
1 5
1 5
1 5
1 5
1 5
1 5
1 5
1 5
1 5
1 5
1 5
1 5
9 1
9 1
9 1
9 1
9 1
9 1
9 1
9 1
9 1
9 1
9 1
9 1
9 1
9 1
9 1
5 9
5 9
5 9
5 9
5 9
5 9
5 9
5 9
5 9
5 9
5 9
5 9
5 9
5 9
5 9
8 1
8 1
9 5
9 5
9 5
9 5
9 5
9 5
9 5
9 5
9 5
9 5
9 5
9 5
9 8
9 8
1 9
1 9
8 1
8 1
9 8
9 8
7 1
8 9
8 7
1 8
7 1
8 7
6 1
7 8
7 9
7 9
7 9
7 9
7 9
7 9
7 9
7 9
7 9
7 9
7 9
7 5
7 5
7 6
1 7
6 1
7 6
4 7
4 7
4 7
4 7
4 7
4 7
4 7
4 7
4 7
4 7
4 7
4 7
4 7
4 7
4 5
4 5
4 9
4 9
4 8
4 7
9 4
10 4
10 9
4 10
4 10
9 4
10 9
6 4
6 4
6 4
6 4
6 4
6 4
6 4
6 4
6 4
6 4
6 4
9 10
9 4
9 6
9 6
9 6
9 6
9 6
9 6
9 6
9 6
9 6
9 6
9 6
4 9
4 9
4 9
4 9
4 9
4 9
4 9
4 9
4 9
4 9
4 9
4 9
6 4
6 4
6 4
6 4
6 4
6 4
6 4
6 4
6 4
6 4
6 4
9 6
9 6
9 6
9 6
9 6
9 6
9 6
9 6
9 6
9 6
9 6
8 4
8 4
8 4
6 9
6 9
6 9
6 9
6 9
6 9
6 9
6 9
6 8
6 8
6 8
4 6
4 6
4 6
8 4
8 4
8 4
6 8
6 8
6 8
5 4
5 4
8 6
8 6
8 6
8 6
8 6
8 6
8 6
8 6
8 9
8 9
8 9
8 9
8 6
8 5
8 6
8 6
8 4
8 5
4 8
4 8
4 8
5 4
5 4
8 5
8 5
7 4
7 4
5 8
5 8
5 8
5 7
5 8
5 7
4 5
4 5
7 4
7 4
5 7
5 7
7 5
7 5
7 5
7 5
7 8
7 8
7 8
7 8
7 8
7 8
7 8
7 8
7 8
7 8
7 8
7 4
7 8
7 8
7 5
7 5
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
10 7
10 8
10 8
10 7
10 7
10 8
10 8
10 8
10 8
10 8
10 8
10 8
10 8
10 8
10 8
10 8
10 8
10 8
10 8
10 8
7 10
7 10
7 10
7 10
7 10
7 10
7 10
7 10
7 10
7 10
7 10
7 10
7 10
7 10
7 10
7 10
7 10
7 10
7 10
7 10
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
8 7
10 8
10 8
10 8
10 8
10 8
10 8
10 8
10 8
10 8
10 8
10 8
10 8
10 8
10 8
10 8
10 8
10 8
6 7
6 7
8 10
8 10
8 10
8 10
8 10
8 10
8 10
8 10
8 10
8 10
8 6
8 10
8 10
8 10
8 10
8 10
8 10
8 6
7 8
7 8
6 7
6 7
8 6
8 6
9 7
6 8
6 8
6 8
6 8
6 8
6 8
6 8
6 8
6 8
6 9
7 6
9 7
6 9
5 6
5 6
5 6
5 6
5 6
5 6
5 6
5 6
5 6
5 8
5 8
5 8
5 8
5 8
5 8
5 8
5 10
5 8
5 8
5 6
9 5
9 5
9 5
9 5
10 5
10 9
10 5
10 9
10 5
10 9
10 5
10 5
10 5
10 5
10 5
10 5
10 5
10 9
5 10
5 10
5 10
5 10
5 10
5 10
5 10
5 10
5 10
5 10
5 10
5 10
5 10
5 10
9 5
9 5
9 5
9 5
10 9
10 9
10 9
10 9
6 5
6 5
6 5
6 5
6 5
6 5
6 5
6 5
6 5
9 10
9 10
9 10
9 10
9 6
9 6
9 6
9 6
9 6
9 6
9 6
9 6
9 5
9 5
9 6
5 9
5 9
5 9
5 9
5 9
5 9
5 9
5 9
5 9
5 9
5 9
6 5
6 5
6 5
6 5
6 5
6 5
6 5
6 5
6 5
9 6
9 6
9 6
9 6
9 6
9 6
9 6
9 6
9 6
8 5
8 5
8 5
8 5
8 5
6 9
6 9
6 9
6 9
6 9
6 9
6 9
6 9
6 9
6 9
6 9
6 8
6 8
6 8
6 8
6 8
5 6
5 6
5 6
5 6
5 6
8 5
8 5
8 5
8 5
8 5
6 8
6 8
6 8
6 8
6 8
8 6
8 6
8 6
8 6
8 6
8 6
8 6
8 6
8 6
8 6
8 6
8 9
8 9
8 6
8 6
8 6
8 5
8 5
8 6
8 6
9 8
9 8
9 8
9 8
9 8
9 8
9 8
9 8
9 8
9 8
9 8
9 8
9 8
10 8
10 8
10 8
10 8
10 8
10 9
10 9
10 8
10 9
10 9
10 9
10 9
10 9
10 9
10 9
10 9
10 9
10 9
10 8
10 9
8 10
8 10
8 10
8 10
8 10
8 10
8 10
8 10
8 10
8 10
8 10
8 10
8 10
8 10
8 10
8 10
8 10
8 10
8 10
8 10
9 8
9 8
9 8
9 8
9 8
9 8
9 8
9 8
9 8
9 8
9 8
9 8
9 8
10 9
10 9
10 9
10 9
10 9
10 9
10 9
10 9
10 9
10 9
10 9
10 9
10 9
6 8
6 8
6 8
6 8
6 8
9 10
9 6
9 6
9 6
9 6
9 10
9 10
9 10
9 10
9 10
9 10
9 10
9 10
9 6
8 9
8 9
8 9
8 9
8 9
6 8
6 8
6 8
6 8
6 8
9 6
9 6
9 6
9 6
9 6
6 9
6 9
6 9
6 9
6 9
6 9
6 8
6 9
6 9
6 9
6 10
6 8
6 10
6 10
6 10
6 9
6 9
6 9
6 9
6 9
9 6
9 6
9 6
9 6
9 6
9 6
9 6
9 6
9 6
9 6
10 6
10 6
10 6
10 6
10 9
10 9
10 9
10 9
10 9
10 6
10 6
10 6
10 6
10 9
10 9
10 9
10 9
10 9
6 10
6 10
6 10
6 10
6 10
6 10
6 10
6 10
6 10
6 10
6 10
6 10
6 10
6 10
6 10
6 10
6 10
6 10
9 6
9 6
9 6
9 6
9 6
9 6
9 6
9 6
9 6
9 6
10 9
10 9
10 9
10 9
10 9
10 9
10 9
10 9
10 9
10 9
9 6
9 6
9 10
9 10
9 10
9 10
9 6
9 6
9 6
9 6
9 10
9 6
9 6
9 6
9 6
9 10
9 10
9 10
9 10
9 10

提示

柱子中的内容为：按自底向上的顺序依次给出柱子上每个球的颜色。 【样例 1 解释】

【校验器】这里不提供了 为了方便选手测试，在ball 目录下我们下发了checker.cpp 文件，选手可以编译该 程序，并使用它校验自己的输出文件。但请注意它与最终评测时所使用的校验器并不完 全一致。你也不需要关心其代码的具体内容。 编译命令为：g++ checker.cpp −o checker。 checker 的使用方式为：checker ，参数依次表示输入文 件与你的输出文件。 若你输出的数字大小范围不合法，则校验器会给出相应提示。若你的输出数字大小 范围正确，但方案错误，则校验器会给出简要的错误信息：

  1. A x，表示进行到第 x 个操作时不合法。
  2. B x，表示操作执行完毕后第 x 个柱子上的球不合法。 若你的方案正确，校验器会给出OK。
上一题 下一题
请先登陆