#763 Matrice3 pbinfo
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
Răspunsuri la întrebare
Răspuns:
#include <iostream>
using namespace std;
int a[101][101], slines[101], rez[101][4];
int main()
{
int n, m, k, i, j, frmax=0, s, p, x, sfrmax=0;
cin >> n >> m >> k;
for (i=1; i<=n; ++i)
for (j=1; j<=m; ++j)
cin >> a[i][j];
for (i=1; i<=n; ++i)
{
s=0;
for (j=1; j<=m; ++j)
s+=a[i][j];
slines[i]=s;
}
int fr;
for (i=1; i<n; ++i)
{
fr=1;
for (j=i+1; j<=n; ++j)
if (slines[i]==slines[j]) ++fr;
if (fr>frmax) {frmax=fr; sfrmax=slines[i]; }
}
p=0;
int dif;
for (i=1; i<=n; ++i)
{
if (slines[i]!=sfrmax)
{
if (sfrmax>slines[i])
{
dif=sfrmax-slines[i];
j=1; while (a[i][j]+dif>=1000000) ++j;
x=a[i][j]+dif; ++p;
rez[p][1]=i; rez[p][2]=j; rez[p][3]=x;
}
else
{
dif=slines[i]-sfrmax;
j=1;
int maxline=a[i][j], poz=j, z;
for (z=j+1; z<=m; ++z)
if (a[i][z]>maxline) { maxline=a[i][z]; poz=z; }
if (dif<=maxline)
{
j=1;
while (a[i][j]-dif<0) ++j;
x=a[i][j]-dif; ++p;
rez[p][1]=i; rez[p][2]=j; rez[p][3]=x;
}
else
{
j=1;
dif=dif-a[i][j]; a[i][j]=0; x=0; ++p;
rez[p][1]=i; rez[p][2]=j; rez[p][3]=x;
x=a[i][poz]-dif;a[i][poz]=x; ++p;
rez[p][1]=i; rez[p][2]=poz; rez[p][3]=x;
}
}
}
}
cout << p << "\n";
for (i=1; i<=p; ++i)
cout << rez[i][1] << " " << rez[i][2] << " " << rez[i][3] << "\n";
return 0;
}
Explicație: