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 ≤ 1001 ≤ 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
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema Matrice3:
#include <iostream>
using namespace std;
int a[101][101], n, m , k , p , L[101], C[101], X[101];
int main(){
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];
}
p = 0;
if(k == n-1)
{
//este posibil ca toate liniile sa aibe sume diferite
// determinam suma maxima SMAX
// toate celelalte linii se vor modifica astfel incat sa se obtina suma SMAX.
// pe fiecare linie va creste cel mai mic element
int SMAX = 0;
for(int i = 1 ; i <= n ; ++i)
if(a[i][0] > SMAX)
SMAX = a[i][0];
for(int i = 1 ; i <= n ; ++i)
if(a[i][0] != SMAX)
{
int jmin = 1;
for(int j = 2 ; j <= m ; ++j)
if(a[i][j] < a[i][jmin])
jmin = j;
++p; L[p] = i, C[p] = jmin, X[p] = a[i][jmin]+(SMAX - a[i][0]);
}
}
else
{
// trebuie sa existe cel putin n-k linii cu aceeasi suma a elementelor
//determinam suma care apare de cel putin n-k ori. fie aceasta S
// pentru celelalte linii vom modifica cate un element
//daca suma este mai mica decat S, marim cel mai mic element, daca suma este mai mare decat S micsoram cel mai mare element. Daca nu ajunge, continuam cu micsorarea
int S = -1;
for(int i = 1 ; i <= n && S == -1 ; 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)
{
// vom mari un element
int jmin = 1;
for(int j = 2 ; j <= m ; ++j)
if(a[i][j] < a[i][jmin])
jmin = j;
int plus = S - a[i][0];
a[i][jmin] += plus;
++p; L[p] = i, C[p] = jmin, X[p] = a[i][jmin];
}
else
while(a[i][0] > S)
{
//vom micsora un element
int jmax = 1;
for(int j = 2 ; j <= m ; ++j)
if(a[i][j] > a[i][jmax])
jmax = j;
int dif;
if(a[i][0] - S <= a[i][jmax])
dif = a[i][0] - S;
else
dif = a[i][jmax];
a[i][jmax] -= dif;
a[i][0] -= dif;
++p; L[p] = i, C[p] = jmax, X[p] = a[i][jmax];
}
}
cout << p << endl;
for(int i =1 ; i <= p ; i ++)
cout <<L[i] << " " << C[i] << " " << X[i] << endl;
return 0;
}
Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #763 Matrice3
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #763 Matrice3 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!