Fişierul intrare/ieşire:echilibrare.in, echilibrare.outSursăLot Măgurele 2016 - Baraj 5 Seniori
AutorAdrian Panaete, Mihai CalanceaAdăugată deatatomirTatomir Alex atatomir
Timp execuţie pe test0.2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Echilibrare

Se consideră o matrice A = (ai,j), 1 ≤ i, j ≤ n  (matrice pătratică de ordin n cu liniile şi coloanele indexate de la 1 la n).
Se cere să se construiască o matrice matrice B = (bi,j), 1 ≤ i, j ≤ n  cu următoarele proprietăţi.

  1. (ai,j)(bi,j), ∀ 1 ≤ i, j ≤ n
  2. (bi,j) + (bi+1,j+1) = (bi+1,j) + (bi,j+1), ∀ 1 ≤ i, j ≤ n - 1 ( o matrice cu această proprietate se numeşte matrice echilibrată )
  3. Suma elementelor din matricea B este minimă. ( adică orice matrice care îndeplineşte primele două condiţii are suma elementelor mai mare sau egală decât suma elementelor matricei B).

Cerinţă

Cunoscând o matrice oarecare cu elementle numere naturale să se determine o altă matrice echilibrată cu elementele numere naturale îndeplinind condiţiile din enunţ.

Date de intrare

Fisierul de intrare echilibrare.in va contine pe prima linie numarul n cu semnificatie din enunt. Vor urma n linii fiecare conţinând câte n numere naturale separate prin câte un spaţiu. Cele n linii conţin elementele liniilor corespunzătoare din matricea iniţiala.

Date de ieşire

Fişierul de ieşire echilibrare.out va conţine pe prima linie un singur număr reprezentând suma elementelor din matricea echilibrată cerută. Următoarele n linii vor conţine câte n numere naturale separate prin spaţiu reprezentănd elementele din matricea echilibrată găsită.

Restricţii

  • 1 ≤ n≤ 50
  • Elementele din matricea iniţială sunt numere naturale cu valori mai mici sau egale decât 35000.
  • Elementele din matricea finală sunt numere naturale şi valoarea lor poate depăşi 35000.
  • Dacă există mai multe soluţii corecte se poate afişa oricare dintre acestea.
  • Daca se determină doar suma corectă se vor obţine 60 de puncte.

Exemplu

echilibrare.inechilibrare.outExemplu
4
1 1 1 1
1 1 1 1
1 1 1 0
1 1 1 1
16
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
Matricea din fişierul de ieşire are suma elementelor 16 ,
are fiecare element mai mare sau egal decât elementul corespunzător al matricii din fişierul de intrare,
este echilibrată şi are suma elementelor minimă posibil.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?