Make Them Equal
题意翻译
- 给出一个序列 $a$,求出一个长度不超过 $3n$ 的操作序列,使序列 $a$ 中每个元素相等。
- 定义一次操作为:选出 $(i,j,x)$ 三元组,满足 $i,j$ 为序列合法下标,$x$ 为 $10^9$ 以内非负整数,令 $a_i:= a_i-x\cdot i,a_j:=a_j+x\cdot i$。
- 必须保证操作过程中的任意时刻序列 $a$ 中每个元素都非负。
- 输出时先输出操作次数 $k$,然后输出 $k$ 行操作序列。
- 数据组数 $t\le10^4$,序列长度 $n\le10^4$,元素大小 $1\le a_i\le10^5$。
题目描述
You are given an array $ a $ consisting of $ n $ positive integers, numbered from $ 1 $ to $ n $ . You can perform the following operation no more than $ 3n $ times:
1. choose three integers $ i $ , $ j $ and $ x $ ( $ 1 \le i, j \le n $ ; $ 0 \le x \le 10^9 $ );
2. assign $ a_i := a_i - x \cdot i $ , $ a_j := a_j + x \cdot i $ .
After each operation, all elements of the array should be non-negative.
Can you find a sequence of no more than $ 3n $ operations after which all elements of the array are equal?
输入输出格式
输入格式
The first line contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. Then $ t $ test cases follow.
The first line of each test case contains one integer $ n $ ( $ 1 \le n \le 10^4 $ ) — the number of elements in the array. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^5 $ ) — the elements of the array.
It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^4 $ .
输出格式
For each test case print the answer to it as follows:
- if there is no suitable sequence of operations, print $ -1 $ ;
- otherwise, print one integer $ k $ ( $ 0 \le k \le 3n $ ) — the number of operations in the sequence. Then print $ k $ lines, the $ m $ -th of which should contain three integers $ i $ , $ j $ and $ x $ ( $ 1 \le i, j \le n $ ; $ 0 \le x \le 10^9 $ ) for the $ m $ -th operation.
If there are multiple suitable sequences of operations, print any of them. Note that you don't have to minimize $ k $ .
输入输出样例
输入样例 #1
3
4
2 16 4 18
6
1 2 3 4 5 6
5
11 19 1 1 3
输出样例 #1
2
4 1 2
2 3 3
-1
4
1 2 4
2 4 5
2 3 3
4 5 1