← 返回题目列表

Codeforces · 1799/B

B. 除法均衡

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

给定一个正整数数组 $$$a_1, a_2, \ldots, a_n$$$。

您可以多次(可能为零)执行此操作:

- 选择两个索引 $$$i$$$, $$$j$$$ ($$$1 \leq i, j \leq n$$$, $$$i \neq j$$$)。
- 分配 $$$a_i := \lceil \frac{a_i}{a_j} \rceil$$$。这里 $$$\lceil x \rceil$$$ 表示 $$$x$$$ 四舍五入到最小整数 $$$\geq x$$$。

是否可以通过某些操作序列(可能为空)使所有数组元素相等?如果是,请打印最多 $$$30n$$$ 操作中执行此操作的任何方法。

可以证明,在问题约束下,如果存在某种方法使所有元素相等,则存在最多$$$30n$$$操作的方法。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例描述的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 100$$$)。

每个测试用例描述的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$1000$$$。

输出

对于每个测试用例,打印一个整数 $$$q$$$ ($$$-1 \leq q \leq 30n$$$)。如果$$$q=-1$$$则无解,否则$$$q$$$等于运算次数。

如果 $$$q \geq 0$$$,则在接下来的 $$$q$$$ 行中打印两个整数 $$$i$$$, $$$j$$$ ($$$1 \leq i, j \leq n$$$, $$$i \neq j$$$) — 操作描述。

如果有多个解决方案,您可以打印任意一个。

示例

输入 #1

10
1
100
3
1 1 1
2
2 1
2
5 5
3
4 3 2
4
3 3 4 4
2
2 100
5
5 3 6 7 8
6
3 3 80 3 8 3
4
19 40 19 55

输出 #1

0
0
-1
0
2
1 3
2 1
4
3 1
4 2
1 3
2 4
6
2 1
2 1
2 1
2 1
2 1
2 1
8
5 2
4 2
3 2
1 3
1 3
2 1
4 1
5 1
4
5 1
3 1
3 1
3 1
9
4 2
2 1
1 2
1 2
3 2
3 2
1 4
2 4
3 4

注意

在第一个、第二个、第四个测试用例中,所有数字都相等,因此可以什么都不做。

在第三个测试用例中,不可能使所有数字相等。

在第五个测试用例中:$$$[\color{red}{4}, 3, \color{blue}{2}] \to [\color{blue}{2}, \color{red}{3}, 2] \to [2, 2, 2]$$$。

在第六个测试用例中: $$$[\color{blue}{3}, 3, \color{red}{4}, 4] \to [3, \color{blue}{3}, 2, \color{red}{4}] \to [\color{red}{3}, 3, \color{blue}{2}, 2] \to [2, \color{red}{3}, 2, \color{blue}{2}] \ 到 [2, 2, 2, 2]$$$。

这里红色数字是 $$$i$$$ 索引(将被分配),蓝色数字是 $$$j$$$ 索引。