TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P7724
  • 题目
  • P7724「NOIP2020」移球游戏
    限制 : 时间限制 : - MS   空间限制 : 524288 KB  SPJ
    评测说明 : 1s,512MB
    问题描述

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

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

    校验器

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

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

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

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

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

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