また変な設定の問題。
https://codeforces.com/contest/1416/problem/B
問題
1-originの整数列Aが与えられる。
このAに以下の処理を繰り返す。
- A[i]からiの倍数である正整数を引き、その分をA[j]に足す
Aを3*|A|回以下の処理で全要素等しくできるか判定せよ。
解法
まず全要素の総和が|A|の倍数であることが前提。
A[1]にすべてを集めてしまえば、そこから各要素に値をばらまくのは簡単。
そこでまずA[1]にすべて集めよう。
A[i]→A[1]に値を集めるとき、A[i]がiの倍数でない場合は、不足分をいったんA[1]から借りればよい。
int T; int N; int A[10101]; void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>N; int sum=0; FOR(i,N) { cin>>A[i+1]; sum+=A[i+1]; } if(sum%N) { cout<<-1<<endl; continue; } sum/=N; vector<vector<int>> V; for(i=2;i<=N;i++) { int lef=(i-A[i]%i)%i; V.push_back({1,i,lef}); A[1]-=lef; A[i]+=lef; V.push_back({i,1,A[i]/i}); A[1]+=A[i]; A[i]=0; } assert(A[1]==sum*N); for(i=2;i<=N;i++) { assert(A[i]==0); V.push_back({1,i,sum}); } cout<<V.size()<<endl; FORR(v,V) cout<<v[0]<<" "<<v[1]<<" "<<v[2]<<endl; } }
まとめ
解いたのすでに14か月以上前だしなぁ。