[ZSHOI-R1] 河外塔（加强版）

Luogu

IDLGP9452

Time1000ms

Memory256MB

DifficultyP5

Special Judge

但是，你可能没有听过河外塔问题。虽然但是，好像并没有河外塔问题。于是，伟大的 X_Xy 决定创造一个河外塔问题。既然是河内塔问题的延申，就得有些一样的东西：有三个柱子 $A$，$B$ 和 $C$ ，以及 $n$ 个圆盘，其中编号为 $i$ 的圆盘的半径长为 $i$，这些圆盘最开始都在 $A$ 上，最终都要顺序（即从上往下从小到大）地移到 $C$ 上。既然是河内塔问题的延伸，就得有些不同的东西：最开始在 $A$ 上面的圆盘并不是顺序的，由于这个限制，我们也不在意移动过程中的顺序，也就意味着你可以将一个大的圆盘放在小的圆盘上。但是 X_Xy 很懒，他只想让你操作至多 $10^6$ 次。 ## Input 输入共两行。第一行有一个数 $n$，表示圆盘的数量。第二行有 $n$ 个数，表示 $A$ 上所有的圆盘**从上往下**的标号，保证圆盘构成一个 $1\sim n$ 的排列。 ## Output 共若干行。第一行有一个数 $tot$，表示你的操作数。接下来的第 $2$ 到第 $tot$ 行，每行两个用空格隔开的大写字母，第 $i+1$ 行表示你的第 $i$ 次操作是从某立柱移到了另一个上。 [samples] ## Background 河内塔（又称汉诺塔）问题，就是在一块木板上有三个立柱，在柱 1 上放着三个圆盘，小的在上面，大的在下面（初始状态）。让被试将在柱 1 上的三个圆盘移到柱 3 上面（目标状态）。条件是：每次只能移动任何一个柱子上面的一个圆盘，但大的圆盘不能放在小的圆盘上。通用问题解决者的解决过程即是手段——目的分析的策略。 ## Note 对于所有数据点：$1\leqslant n \leqslant 4\times 10^4$ | 数据点 | n | | :----------: | :----------: | | 1~2 | $\leqslant 10$ | | 3~4 | $\leqslant 200$ | | 5~7 | $\leqslant 3\times 10^4 $ | | 8~10 | $\leqslant 4\times 10^4 $ |

Samples

Input #1

3
1 2 3

Output #1

5
A B
A B
A C
B C
B C

API Response (JSON)

{
  "problem": {
    "name": "[ZSHOI-R1] 河外塔（加强版）",
    "description": {
      "content": "但是，你可能没有听过河外塔问题。虽然但是，好像并没有河外塔问题。于是，伟大的 X_Xy 决定创造一个河外塔问题。 既然是河内塔问题的延申，就得有些一样的东西：有三个柱子  $A$，$B$ 和 $C$ ，以及 $n$ 个圆盘，其中编号为 $i$ 的圆盘的半径长为 $i$，这些圆盘最开始都在 $A$ 上，最终都要顺序（即从上往下从小到大）地移到 $C$ 上。 既然是河内塔问题的延伸，就得有些不同的",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9452"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "但是，你可能没有听过河外塔问题。虽然但是，好像并没有河外塔问题。于是，伟大的 X_Xy 决定创造一个河外塔问题。\n\n既然是河内塔问题的延申，就得有些一样的东西：有三个柱子 \n$A$，$B$ 和 $C$ ，以及 $n$ 个圆盘，其中编号为 $i$ 的圆盘的半径长为 $i$，这些圆盘最开始都在 $A$ 上，最终都要顺序（即从上往下从小到大）地移到 $C$ 上。\n\n既然是河内塔问题的延伸，就得有些不同的...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments