考察

\(A_1 + \dots + A_N\) が \(N\) の倍数でなければ不可能であり，\(N\) の倍数であれば可能です．

\(X := \displaystyle \frac{A_1 + \dots + A_N}{N}\) とします．問題文中の条件は，すべての要素 \(a_1, \dots, a_N\) を \(X\) に等しくすることと言い換えられます(ここでは，操作の対象となる数列を \(a_1, \dots, a_N\)，入力で与えられる初期値を \(A_1, \dots, A_N\) とおいて区別します)．

ある操作列 \((x_1, y_1, z_1), \dots, (x_q, y_q, z_q)\) が条件を満たすとします．このとき，\(N\) 頂点のグラフであって，\(q\) 組の頂点組 \((x_1, y_1), \dots, (x_q, y_q)\) それぞれのあいだに辺を張ったものを考え，その連結成分を \(V_1, \dots, V_s\) とします．このとき，各連結成分 \(V_k\) において，

\[\sum_{v \in V_k} A_v = X \times |V_k|\]

が成り立ちます(操作前後で連結成分内の \(a_v\) の和は変わらず，操作がすべて終わった時点ですべての \(a_v\) は \(X\) に等しい)． また，連結成分 \(V_k\) がもつ辺の本数は \(|V_k| - 1\) 以上であるため，グラフ全体の辺の本数は \(N - s\) 以上です．

逆に，子供たちの分割 \(V_1 \sqcup \dots \sqcup V_S = \{1, \dots, N\}\) であって，各部分集合 \(V_k\) が \(\sum_{v \in V_k} A_v = X \times |V_k|\) を満たすものが与えられたとき，以下のようにして問題文中の条件を満たす長さ \(N - s\) の操作列を構築することができます．

• 各部分集合 \(V_k\) に属する \(t := |V_k|\) 人の子供を，\(A_{v_{k,i}}\) の降順に \(v_{k, 1}, \dots, v_{k, t}\) とする．\(i = 1, \dots, t-1\) の昇順に，以下の整数組 \((x,y,z)\) によって操作 \((x,y,z)\) を行う．
  • \(x := v_{k,i}\) および \(y := v_{k,i+1}\) とし，\(z := a_{x} - X\) とする(ここで常に \(z \geq 0\) が成り立つことは，\(v_{k,i}\) が降順であることから示せる)．

よって，多重集合 \(A = \{A_1, \dots, A_N\}\) を平均が \(X\) である部分集合に分割する方法であって，最も部分集合の個数 \(s\) が多いものを求め，各部分集合で上の操作を行えばよいです．

• 分割を求めるところは，\(1\) 要素ずつ追加していく bitDP によって \(O(N 2^N)\) 時間で計算できます．
• 操作列を求めるところは，上の操作を実装することで \(O(N \log N)\) 時間で計算できます．

以上より，\(O(N 2^N)\) 時間でこの問題を解くことができ，十分高速です．

実装例 (C++)

#include <iostream>
using std::cin;
using std::cout;
using std::min;
using std::max;
#include <vector>
using std::vector;
using std::pair;
#include <algorithm>
using std::sort;

typedef long long int ll;

ll n;
vector<ll> a;

vector<ll> dp, subsum, dprev;

vector<ll> x, y, z;

void solve () {
	ll sum = 0;
	for (ll i = 0; i < n; i++) {
		sum += a[i];
	}
	if (sum % n != 0) {
		cout << "-1" << "\n";
		return;
	}
	ll avg = sum / n;
	//
	dp.resize(1LL << n);
	subsum.resize(1LL << n);
	dprev.resize(1LL << n);
	dp[0] = 0;
	subsum[0] = 0;
	dprev[0] = -1;
	for (ll b = 1; !(b >> n); b++) {
		dp[b] = n+1;
		dprev[b] = -1;
		
		subsum[b] = 0;
		for (ll i = 0; i < n; i++) {
			if (b & (1LL << i)) subsum[b] += (a[i] - avg);
		}

		ll item = ((subsum[b] == 0) ? 0 : +1);
		for (ll i = 0; i < n; i++) {
			if (b & (1LL << i)) {
				ll maybe = dp[b - (1LL << i)] + item;
				if (dp[b] > maybe) {
					dp[b] = maybe;
					dprev[b] = i;
				}
			}
		}
	}

	ll cb = (1LL << n) - 1;
	while (cb) {
		vector<pair<ll, ll> > v;
		while (true) {
			ll vi = dprev[cb];
			v.push_back({-a[vi], vi}); // a[i] in decreasing order
			cb -= (1LL << vi);

			if (subsum[cb] == 0) break;
		}

		sort(v.begin(), v.end());
		ll carry = a[v[0].second] - avg;
		for (ll i = 1; i < v.size(); i++) {
			x.push_back(v[i-1].second);
			y.push_back(v[i-0].second);
			z.push_back(carry);

			carry += (a[v[i].second] - avg);
		}
	}

	cout << z.size() << "\n";
	for (ll i = 0; i < z.size(); i++) {
		cout << (x[i] + 1) << " " << (y[i] + 1) << " " << z[i] << "\n";
	}
}

int main (void) {
	
	cin >> n;
	a.resize(n);
	for (ll i = 0; i < n; i++) {
		cin >> a[i];
	}

	solve();
	

	return 0;
}