#NOIP2020C. 移球游戏

移球游戏

题目描述

小 C 正在玩一个移球游戏,他面前有 n+1n + 1 根柱子,柱子从 1n+11\sim n + 1 编号,其中 11 号柱子、22 号柱子、\dotsnn 号柱子上各有 mm 个球,它们自底向上放置在柱子上,n+1n + 1 号柱子上初始时没有球。这 n×mn\times m 个球共有 nn 种颜色,每种颜色的球各 mm 个。

初始时一根柱子上的球可能是五颜六色的,而小 C 的任务是将所有同种颜色的球移到同一根柱子上,这是唯一的目标,而每种颜色的球最后放置在哪根柱子则没有限制。

小 C 可以通过若干次操作完成这个目标,一次操作能将一个球从一根柱子移到另一根柱子上。更具体地,将 xx 号柱子上的球移动到 yy 号柱子上的要求为:

  1. xx 号柱子上至少有一个球;
  2. yy 号柱子上至多有 m1m - 1 个球;
  3. 只能将 xx 号柱子最上方的球移到 yy 号柱子的最上方。

小 C 的目标并不难完成,因此他决定给自己加加难度:在完成目标的基础上,使用的操作次数不能超过 820000820000。换句话说,小 C 需要使用至多 820000820000 次操作完成目标。

小 C 被难住了,但他相信难不倒你,请你给出一个操作方案完成小 C 的目标。合法的方案可能有多种,你只需要给出任意一种,题目保证一定存在一个合法方案。

输入格式

从文件 ball.in 中读入数据。

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

输出格式

输出到文件 ball.out 中。

本题采用自定义校验器(Special Judge)评测。
你的输出的第一行应该仅包含单个整数 kk,表示你的方案的操作次数。你应保证 0k8200000\le k\le 820000
接下来 kk 行每行你应输出两个用单个空格分隔的正整数 x,yx, y,表示这次操作将 xx 号柱子最上方的球移动到 yy 号柱子最上方。你应保证 1x,yn+11\le x, y\le n + 1xyx \neq y

2 3
1 1 2
2 1 2
6
1 3
2 3
2 3
3 1
3 2
3 2

样例说明 1

柱子中的内容为:按自底向上的顺序依次给出柱子上每个球的颜色。

操作 11 号柱子 22 号柱子 33 号柱子
初始 1 1 21\ 1\ 2 2 1 22\ 1\ 2
1 31\ 3 1 11\ 1 2 1 22\ 1\ 2 22
2 32\ 3 1 11\ 1 2 12\ 1 2 22\ 2
2 32\ 3 1 11\ 1 22 2 2 12\ 2\ 1
3 13\ 1 1 1 11\ 1\ 1 22 2 22\ 2
3 23\ 2 1 1 11\ 1\ 1 2 22\ 2 22
3 23\ 2 1 1 11\ 1\ 1 2 2 22\ 2\ 2

样例 2

见附加文件中的 ball2.inball2.ans

样例 3

见附加文件中的 ball3.inball3.ans

数据范围与提示

测试点编号 nn\le mm\le
121\sim 2 22 2020
353\sim 5 1010
686\sim 8 5050 8585
9149\sim 14 300300
152015\sim 20 400400

对于所有测试点,保证 2n502\le n\le 502m4002\le m\le 400

校验器

为了方便选手测试,在下发文件中我们下发了 checker.cpp 文件,选手可以编译该程序,并使用它校验自己的输出文件。但请注意它与最终评测时所使用的校验器并不完全一致。你也不需要关心其代码的具体内容。

编译命令为:g++ checker.cpp -o checker -std=c++11

checker 的使用方式为:checker <inputfile> <outputfile>,参数依次表示输入文件与你的输出文件。

若你输出的数字大小范围不合法,则校验器会给出相应提示。若你的输出数字大小范围正确,但方案错误,则校验器会给出简要的错误信息:

  1. A x,表示进行到第 xx 个操作时不合法。
  2. B x,表示操作执行完毕后第 xx 个柱子上的球不合法。

若你的方案正确,校验器会给出 OK