Cerința

Se dă o matrice cu n linii și m coloane și elemente numere naturale și o valoare k. Să se modifice cel mult k elemente ale matricei, astfel încât toate liniile matricei să aibă aceeași sumă a elementelor.

Date de intrare

Programul citește de la tastatură numerele n m k, apoi elementele matricei, linie cu linie.

Date de ieșire

Programul va afișa pe ecran numărul numărul de elemente modificate, p, apoi p triplete i j x, cu semnificația: elementul din matrice de pe linia i și coloana j devine x. x trebuie să fie număr natural.

Restricții și precizări

• 1 ≤ n , m ≤ 100
• 1 ≤ k < n
• elementele matricei vor fi mai mici decât 1.000.000
• liniile și coloanele matricei sunt numerotate de la 1
• pentru toate datele de test există soluție

Exemplu

Intrare

3 4 2
7 4 1 6
5 5 7 3
4 7 2 3

Ieșire

2
1 3 3
3 1 8

#include <bits/stdc++.h>
using namespace std;
int a1[101], a2[101], a3[101] , p , x;
int main()
{


   int n, m, k, a[101][101];
   cin >> n >> m >> k;
   for(int i = 1; i <= n ; i++)for(int j = 1; j <= m; j++) cin >> a[i][j];
   for(int i = 1; i <= n ; i++)
    {
        a[i][0] = 0;
        for(int j = 1; j <= m ; j++) a[i][0] += a[i][j];
    }
   if(k == n-1)
   {
       int s1 = 0;
       for(int i = 1; i <= n; i++) if(a[i][0] > s1) s1 = a[i][0];
       for(int i = 1; i <= n; i++)
        if(a[i][0] != s1)
       {
           int jmin = 1;
           for(int j = 2; j <= m ; j++) if(a[i][j] < a[i][jmin]) jmin = j;
           p++;
           a1[p] = i;
           a2[p] = jmin;
           a3[p] = a[i][jmin] + s1 - a[i][0];
       }
   }
   else
    {
        int s = 0;
        for(int i = 1; i <= n ; i++)
        {
            int cnt =1;
            for(int j = 1; j <= n; j++) if(a[i][0] == a[j][0])cnt++;
            if(cnt >=n - k) s = a[i][0];
        }

       for(int i=1; i<=n; i++)
        if(a[i][0] < s)
       {
           int jmin = 1;
           for(int j = 2; j <= m; j++) if(a[i][j] < a[i][jmin])jmin = j;
           a[i][jmin] += s-a[i][0];
           p++;
           a1[p] = i;
           a2[p]= jmin;
           a3[p] = a[i][jmin];
       }
       else
        while(a[i][0] > s)
       {
           int jmax = 1;
           for(int j = 2; j <= m; j++)if(a[i][j] > a[i][jmax]) jmax = j;
           if(a[i][0] - s <= a[i][jmax]) x = a[i][0] - s;
           else x = a[i][jmax];
           a[i][jmax] -= x;
           a[i][0] -=x;
           p++;
           a1[p] = i;
           a2[p] = jmax;
           a3[p] = a[i][jmax];

       }

    }
   cout << p << endl;
   for(int i = 1 ; i <= p ; i++)
    cout << a1[i] << " " << a2[i] << " " << a3[i] << endl;



    return 0;
}