CF1416B-Make Them Equal

题目:

题目描述:

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:

1
2
3
4
5
6
7

3
4
2 16 4 18
6
1 2 3 4 5 6
5
11 19 1 1 3

样例输出 1:

1
2
3
4
5
6
7
8
9

2
4 1 2
2 3 3
-1
4
1 2 4
2 4 5
2 3 3
4 5 1

思路:

实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

#include "ybwhead/ios.h"
#define ll long long
const int maxn = 4e4 + 10;
int n;
ll a[maxn], b[maxn], c[maxn], d[maxn];
int cnt;
void pp(ll x, ll y, ll z)
{
    ++cnt;
    b[cnt] = x;
    c[cnt] = y;
    d[cnt] = z;
}
void pr()
{
    yout << cnt << endl;
    for (int i = 1; i <= cnt; i++)
    {
        yout << b[i] << " " << c[i] << ' ' << d[i] << endl;
    }
}
int main()
{
    int TTT;
    yin >> TTT;
    while (TTT--)
    {
        cnt = 0;
        ll sum = 0;
        yin >> n;
        for (int i = 1; i <= n; i++)
            yin >> a[i], sum += a[i];
        if (sum % n)
        {
            yout << -1 << endl;
            continue;
        }
        sum /= n;
        for (int i = 2; i <= n; i++)
        {
            if (a[i] % i == 0)
            {
                pp(i, 1, a[i] / i);
            }
            else
            {
                pp(1, i, i - a[i] % i);
                pp(i, 1, a[i] / i + 1);
            }
        }
        for (int i = 2; i <= n; i++)
            pp(1, i, sum);
        pr();
    }
}