← 返回题目列表

Codeforces · 2034/D

D. 大流士的智慧

中文机器翻译题面 查看原题

大流士大帝正在建造 $$$n$$$ 石柱,每根石柱都由一个基座和堆叠在顶部的 $$$0$$$、$$$1$$$ 或 $$$2$$$ 铭文组成。

在每次移动中,Darius 可以选择两列 $$$u$$$ 和 $$$v$$$,使得这些列之间的铭文数量差异恰好为 $$$1$$$,并将一个铭文从铭文较多的列转移到另一列。保证至少一列恰好包含 $$$1$$$ 铭文。

由于美观是历史建筑的主要支柱,Darius 希望柱子的高度不断上升。为了避免工人付出过多的努力,他要求你计划一系列最多 $$$n$$$ 的移动,根据铭文的数量以非递减的顺序排列柱子。不需要最小化移动次数。

输入

第一行包含一个整数 $$$t$$$ — 测试用例的数量。 ($$$1 \leq t \leq 3000$$$)

每个测试用例的第一行包含一个整数 $$$n$$$ — 石柱的数量。 ($$$1 \leq n \leq 2 \cdot 10^5$$$)

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$,其中 $$$a_i \in \{0,1,2\}$$$ 表示第 $$$i$$$ 列中的初始铭文数量。保证至少有一列恰好有 $$$1$$$ 铭文。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 $$$k$$$ — 用于对列进行排序的移动次数。 ($$$0 \leq k \leq n$$$)

然后,输出 $$$k$$$ 行,每行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$),表示第 $$$i$$$ 移动中涉及的列的索引。在每次移动过程中,它必须保持 $$$|a_{u_i} - a_{v_i}| = 1$$$,一个铭文从具有更多铭文的列转移到另一列。

可以证明,在给定的约束条件下,始终存在有效的解。

示例

输入 #1

3
4
0 2 0 1
3
1 2 0
6
0 1 1 2 2 2

输出 #1

2
2 4
2 3
2
3 1
2 3
0

注意

第一个测试用例中的列状态:

- 初始:$$$0, 2, 0, 1$$$
- 第一次移动后:$$$0, 1, 0, 2$$$
- 第二次移动后:$$$0, 0, 1, 2$$$

第二个测试用例中的列状态:

- 初始:$$$1, 2, 0$$$
- 第一步之后:$$$0, 2, 1$$$
- 第二次移动后:$$$0, 1, 2$$$

在第三个测试用例中,列高已按升序排序。