← 返回题目列表

Codeforces · 1342/F

F. 使其上升

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

给定一个由 $$$n$$$ 元素组成的数组 $$$a$$$。您可以对其应用多个操作(可能为零)。

在每次操作期间,您选择两个索引 $$$i$$$ 和 $$$j$$$ ($$$1 \le i, j \le n$$$; $$$i \ne j$$$),将 $$$a_j$$$ 增加 $$$a_i$$$,并从数组中删除第 $$$i$$$ 个元素(因此其右侧所有元素的索引减少$$$1$$$ 和 $$$n$$$ 也减少了 $$$1$$$)。

您的目标是使数组 $$$a$$$ 严格升序。也就是说,条件 $$$a_1 < a_2 < \dots < a_n$$$ 应该成立(其中 $$$n$$$ 是数组的结果大小)。

计算使数组严格升序所需的最小操作数。

输入

第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 10000$$$) — 测试用例的数量。

每个测试用例由两行组成。第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 15$$$) — 初始数组 $$$a$$$ 中的元素数量。

第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^6$$$)。

保证:

- 具有 $$$n \ge 5$$$ 的测试用例数量不大于 $$$5000$$$;
- 具有 $$$n \ge 8$$$ 的测试用例数量不大于 $$$500$$$;
- $$$n \ge 10$$$ 的测试用例数量不大于 $$$100$$$;
- 具有 $$$n \ge 11$$$ 的测试用例数量不大于 $$$50$$$;
- $$$n \ge 12$$$ 的测试用例数量不大于 $$$25$$$;
- $$$n \ge 13$$$ 的测试用例数量不大于 $$$10$$$;
- $$$n \ge 14$$$ 的测试用例数量不大于 $$$3$$$;
- 具有 $$$n \ge 15$$$ 的测试用例数量不大于 $$$1$$$。

输出

对于每个测试用例,打印答案如下:

在第一行中,打印 $$$k$$$ — 您必须执行的最少操作数。然后打印$$$k$$$行,每行包含对应操作的两个索引$$$i$$$和$$$j$$$。请注意,从数组中删除元素后,数组中元素的数量会发生变化。如果有多个最佳操作序列,则打印其中任意一个。

示例

输入 #1

4
8
2 1 3 5 1 2 4 5
15
16384 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 1
2
3 3
14
1 2 3 4 5 6 7 8 9 10 11 12 13 14

输出 #1

3
6 8
1 6
4 1
7
1 15
1 13
1 11
1 9
1 7
1 5
1 3
1
2 1
0

注意

在第一个测试用例中,操作顺序 $$$a$$$ 更改如下:

$$$[2, 1, 3, 5, 1, 2, 4, 5] \rightarrow [2, 1, 3, 5, 1, 4, 7] \rightarrow [1, 3, 5, 1, 6, 7] \rightarrow [2, 3, 5, 6, 7]$$$。