Make Them Equal

Created by LXC on Wed Apr 10 15:24:35 2024

https://codeforces.com/problemset/problem/1416/B

ranting: 2000

tag: constructive algorithms, greedy, math

problem

• 给出一个序列 $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\le {10}^4$，序列长度 $n\le {10}^4$，元素大小 $1\le a_i\le {10}^5$。

solution

a的总和必须是n的倍数。

注意到初始时$a_i$至少为1.

我们可以最多两步将$a_i,i>1$的值转移到$a_1$，如果$i|̸a_i$先将$a_i$补充到i的倍数,操作$(1,i,i-a_{i}modi)$，然后操作$(i,1,a_i/i)$。

之后可以操作n-1次，$(1,i,\sum a_i/n)$

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int n;
    cin >> n;
    vector<ll> a(n);
    ll s = 0;
    for (auto& i:a) {
        cin >> i;
        s += i;
    }
    if (s%n) {
        cout << "-1\n";
        return; 
    }
    s /= n;
    vector<vector<ll>> ans;

    auto mv = [&](int u, int v, int x) {
        ans.push_back({u+1, v+1, x});
        a[u] -= x*(u+1);
        a[v] += x*(u+1);
    };
    for (int i=1; i<n; i++) {
        if (a[i]%(i+1)) {
            mv(0, i, i+1-a[i]%(i+1));
        }
        mv(i, 0, a[i]/(i+1));
    }
    // 所有数都在1号
    for (int i=1; i<n; i++) {
        ans.push_back({1, i+1, s});
    }
    cout << ans.size() << "\n";
    for (auto& i:ans) {
        cout << i[0] << " " << i[1] << " " << i[2] << "\n";
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}