UOJ Logo Universal Online Judge

UOJ

#582. 【NOIP2020】移球游戏

统计

小 C 正在玩一个移球游戏,他面前有 $n + 1$ 根柱子,柱子从 $1 \sim n + 1$ 编号,其中 $1$ 号柱子、$2$ 号柱子、……、$n$ 号柱子上各有 $m$ 个球,它们自底向上放置在柱子上,$n + 1$ 号柱子上初始时没有球。这 $n \times m$ 个球共有 $n$ 种颜色,颜色编号为 $1$ 到 $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 \le k \le 820000$。

接下来 $k$ 行每行你应输出两个用单个空格分隔的正整数 $x, y$,表示这次操作将 $x$ 号柱子最上方的球移动到 $y$ 号柱子最上方。你应保证 $1 \le x, y \le n + 1$ 且 $x \ne y$。

样例一

input

2 3
1 1 2
2 1 2

output

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

样例解释一

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

操作 $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$

样例二

见附加文件中的 ex_ball2.in/ans

样例三

见附加文件中的 ex_ball3.in/ans

限制与约定

测试点编号 $n \le$ $m \le$
$1 \sim 2$ $2$ $20$
$3 \sim 5$ $10$ $20$
$6 \sim 8$ $50$ $85$
$9 \sim 14$ $50$ $300$
$15 \sim 20$ $50$ $400$

对于所有测试点,保证 $2 \le n \le 50$,$2 \le m \le 400$,所有球的颜色编号为 $1$ 到 $n$ 之间的整数,且每种颜色的球恰有 $m$ 个。

时间限制:$1 \texttt{s}$

空间限制:$512 \texttt{MB}$

校验器

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

编译命令为:g++ -std=c++11 checker.cpp −o checker。此外,附加文件中有还有名为 testlib.h 的文件,在编译时,请确保该文件与checker.cpp 在同一子目录下。

在终端中,checker 的使用方式为:checker <输入文件名> <输出文件名>。如果你的输入文件名为ball.in,输出文件名为ball.out,则正确的使用方式为 checker ball.in ball.out

若你的方案正确,校验器会给出 OK,否则,该校验器会给出简要的错误信息:

  1. A x,表示进行到第 $x$ 个操作时不合法。
  2. B x,表示操作执行完毕后第 $x$ 个柱子上的球不合法。
  3. 其他错误信息,表示你的输出格式不合法,或数字大小范围不合法,请仔细检查你的输出是否满足题面中的格式与数字范围要求。

下载

附加文件下载