Fişierul intrare/ieşire:	echilibrare.in, echilibrare.out	Sursă	Lot Măgurele 2016 - Baraj 5 Seniori
Autor	Adrian Panaete, Mihai Calancea	Adăugată de	Tatomir Alex •atatomir
Timp execuţie pe test	0.1 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Echilibrare

Se consideră o matrice A = (a_i,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 B = (b_i,j), 1 ≤ i, j ≤ n  cu următoarele proprietăţi.

1. (a_i,j) ≤ (b_i,j), ∀ 1 ≤ i, j ≤ n
2. (b_i,j) + (b_i+1,j+1) = (b_i+1,j) + (b_i,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

Cum se trimit solutii?