P14770 [ICPC 2024 Seoul R] Pair Sorting

有 $n$ 个箱子排成一行，地上有 $2n$ 个球。球的编号从 $1$ 到 $n$，对于每个 $i$ ($1 \leq i \leq n$)，恰好有两个编号为 $i$ 的球。此外，对于 $1 \leq i \leq n$，第 $i$ 个箱子记为 $B_i$，每个箱子 $B_i$ 最多可以容纳两个球。初始时，对于 $1 \leq i \leq n$，箱子 $B_i$ 中包含两个编号为 $n+1-i$ 的球。初始的箱子配置参见下面的图 F.1。 :::align{center}  图 F.1. 箱子的初始配置 ::: 你只能交换相邻两个箱子中的球，这代表一次**交换操作**。请注意，箱子不是栈，对于相邻的箱子 $B_i$ 和 $B_{i+1}$，你可以交换 $B_i$ 中两个球中的一个与 $B_{i+1}$ 中的一个球。参见下面的图 F.2。该图展示了两次交换操作。 :::align{center}  图 F.2. 相邻箱子之间的交换操作 ::: 通过这些交换操作，你需要对球进行排序。排序完成后，对于 $1 \leq i \leq n$，箱子 $B_i$ 必须包含两个编号为 $i$ 的球。特别地，当给定一个关于 $n$ 的函数 $\text{Bound}$ 时（尤其是 $\text{Bound} = 0.7n^2$），交换操作的总数不应超过 $\text{Bound}$。 给定 $n$ 个箱子和 $2n$ 个球，请编写一个程序，找到一种球的排序方法，使得交换操作的总数不超过 $\text{Bound} = 0.7n^2$。

你的程序需要从标准输入读取数据。输入恰好包含一行。该行包含一个整数 $n$ ($3 \leq n \leq 100$)，表示有 $n$ 个箱子和 $2n$ 个球。

你的程序需要向标准输出写入结果。令 $S$ 为你的排序方法中交换操作的总数。输出恰好 $S+1$ 行。第一行包含 $S$。接下来的 $S$ 行，每行包含三个整数 $j, a, b$，表示一次交换操作：交换箱子 $B_j$ 中的球 $a$ 与箱子 $B_{j+1}$ 中的球 $b$，其中 $1 \leq j \leq n-1$，$1 \leq a, b \leq n$。你的排序方法中的交换操作应按顺序逐行打印。数字 $S$ 必须满足 $S \leq 0.7n^2$。

翻译由 DeepSeek V3 完成