CF1854A2.Dual (Hard Version)

Popskyy & tiasu - Dual

⠀

The only difference between the two versions of this problem is the constraint on the maximum number of operations. You can make hacks only if all versions of the problem are solved.

You are given an array $a_1, a_2,\dots, a_n$ of integers (positive, negative or $0$). You can perform multiple operations on the array (possibly $0$ operations).

In one operation, you choose $i, j$ ($1 \leq i, j \leq n$, they can be equal) and set $a_i := a_i + a_j$ (i.e., add $a_j$ to $a_i$).

Make the array non-decreasing (i.e., $a_i \leq a_{i+1}$ for $1 \leq i \leq n-1$) in at most $31$ operations. You do not need to minimize the number of operations.

Popskyy & tiasu - Dual

⠀

本题的两个版本之间唯一的区别在于对最大操作次数的限制。仅当两个版本均已被解决时，才允许进行 Hack。

给定一个由整数（正数、负数或 $0$）构成的数组 $a_1, a_2,\dots, a_n$。你可以对数组执行多次操作（也可以不执行任何操作）。

每次操作中，你选择下标 $i, j$（满足 $1 \leq i, j \leq n$，二者可以相等），并将 $a_i$ 更新为 $a_i + a_j$（即把 $a_j$ 加到 $a_i$ 上）。

请在至多 $31$ 次操作内，使该数组变为非递减数组（即对所有 $1 \leq i \leq n-1$，满足 $a_i \leq a_{i+1}$）。你无需最小化操作次数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.

The first line contains a single integer $n$ ($1 \le n \le 20$) — the length of the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-20 \le a_i \le 20$) — the array before performing the operations.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 500$）。随后是各测试用例的描述。

第一行包含一个整数 $n$（$1 \le n \le 20$）—— 数组的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-20 \le a_i \le 20$）—— 执行操作前的数组。

For each test case, output your operations in the following format.

The first line should contain an integer $k$ ($0 \le k \le 31$) — the number of operations.

The next $k$ lines represent the $k$ operations in order. Each of these $k$ lines should contain two integers $i$ and $j$ ($1 \leq i, j \leq n$) — the corresponding operation consists in adding $a_j$ to $a_i$.

After all the operations, the array $a_1, a_2,\dots, a_n$ must be non-decreasing.

对于每个测试用例，请按以下格式输出你的操作。

第一行应包含一个整数 $k$（$0 \le k \le 31$），表示操作的次数。

接下来的 $k$ 行依次表示这 $k$ 个操作。每行应包含两个整数 $i$ 和 $j$（$1 \leq i, j \leq n$），对应的操作为将 $a_j$ 加到 $a_i$ 上。

执行完所有操作后，数组 $a_1, a_2,\dots, a_n$ 必须是非递减的。

In the first test case, by adding $a_1 = 2$ to $a_2$, we get the array $[2, 3]$ which is non-decreasing.

In the second test case, the array changes as:

• $[1, 2, -10, 3]$
• $[1, 2, -10, 6]$
• $[1, 2, -10, 12]$
• $[1, 2, 2, 12]$

In the third test case, the final array is $[2, 3, 3, 3, 3]$.

在第一个测试用例中，将 $a_1 = 2$ 加到 $a_2$ 上，得到数组 $[2, 3]$，该数组是非递减的。

在第二个测试用例中，数组的变化过程如下：

• $[1, 2, -10, 3]$
• $[1, 2, -10, 6]$
• $[1, 2, -10, 12]$
• $[1, 2, 2, 12]$

在第三个测试用例中，最终数组为 $[2, 3, 3, 3, 3]$。