== include(page="template/taskheader" task_id="echilibrare") ==
Poveste şi cerinţă...
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.
# $(a$~i,j~$)$ ≤ $(b$~i,j~$)$, ∀ 1 ≤ i, j ≤ n
# $(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ă )
# 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$).
h2. 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ţ.
h2. Date de intrare
Fişierul de intrare $echilibrare.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $echilibrare.out$ ...
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ă.
h2. 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.
h2. Exemplu
table(example). |_. echilibrare.in |_. echilibrare.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
table(example). |_. echilibrare.in |_. echilibrare.out |_. Exemplu |
| 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.
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="echilibrare") ==
