==Include(page="template/taskheader" task_id="balans")==
 
==Include(page="template/raw")==
 
Balans
 
 
 
Bronzarel a iesit din spital si este sanatos acum. Imediat dupa ce a iesit s-a intalnit din nou cu bunul sau prieten Zaharel si acestia s-au pus pe rezolvat probleme! Una din problemele pe care au incercat s-o rezolve s-a dovedit prea dificila pentru ei, de aceea vor avea nevoie de ajutorul tau.
 
Fie A o matrice de numere naturale cu N linii si M coloane. Vom defini o matrice B de marime P*Q ca fiind o submatrice a matricii A daca exista numerele (x,y) astfel incat B[i,j]=A[i+x,j+y] pentru 1<=i<=P si 1<=j<=Q. De asemenea, vom defini balansul unei matrici ca fiind raportul dintre suma tuturor elementelor din matrice si numarul acestora.
 
Problema la care s-au chinuit Zaharel si Bronzarel cere sa se determine o submatrice de balans maxim a matrici A, care are cel putin R randuri si C coloane. Fiindca lucrurile nu sunt niciodata asa de "simple", matricea A nu este o matrice oarecare, ci una chiar foarte speciala, si anume randurile si coloanele matricii pot fi permutate circular.
 
h2. Cerinta
 
Determinati submatricea de balans maxim dintr-o matrice data, tinand cont ca randurile si coloanele pot fi permutate circular inainte pentru a obtine un rezultat cat mai favorabil.
 
h2. Date de Intrare
 
Prima linie din fisierul balans.in va contine numerele N,M,R,C reprezetand dimensiunea matricii A si limitele inferioare ale dimensiunilor submatricii cerute. Urmatoarele N linii vor contine cate M numere naturale.
 
h2. Date de Iesire
 
Fiserul balans.out va contine pe o singura linie o valoare reprezentand balansul maxim posibil al unei submatrici. Rezultatul va fi afisat cu 3 zecimale exacte.
 
h2. Restrictii si observatii
 
S 1 <= N, M <= 150
 
S 0 <= R <= N
 
S 0 <= C <= M
 
S 0 <= A[i,j] <= 100.000
 
h2. Exemplu
 
balans.in balans.out Explicatie
3 4 2 1 11.500 Se permuta circular odata randurile si se obtine matricea:
 
15 5 15 8 1 2 1 3
 
1 2 1 3 4 8 8 4
 
4 8 8 4 15 5 15 8

==Include(page="template/taskheader" task_id="balans")==
 
Bronzarel a iesit din spital si este sanatos acum. Imediat dupa ce a iesit s-a intalnit din nou cu bunul sau prieten Zaharel si acestia s-au pus pe rezolvat probleme! Una din problemele pe care au incercat s-o rezolve s-a dovedit prea dificila pentru ei, de aceea vor avea nevoie de ajutorul tau.
 
Fie $A$ o matrice de numere naturale cu $N$ linii si $M$ coloane. Vom defini o matrice $B$ de marime $P*Q$ ca fiind o submatrice a matricii $A$ daca exista numerele $(x,y)$ astfel incat $B{~i,j~} = A{~i+x,j+y~}$ pentru $1≤i≤P$ si $1≤j≤Q$. De asemenea, vom defini balansul unei matrici ca fiind raportul dintre suma tuturor elementelor din matrice si numarul acestora.
 
Problema la care s-au chinuit Zaharel si Bronzarel cere sa se determine o submatrice de balans maxim a matrici $A$, care are cel putin $R$ randuri si $C$ coloane. Fiindca lucrurile nu sunt niciodata asa de "simple", matricea $A$ nu este o matrice oarecare, ci una chiar foarte speciala, si anume randurile si coloanele matricii pot fi permutate circular.
 
h2. Cerinta
 
Determinati submatricea de balans maxim dintr-o matrice data, tinand cont ca randurile si coloanele pot fi permutate circular inainte pentru a obtine un rezultat cat mai favorabil.
 
h2. Date de Intrare
 
Prima linie din fisierul $balans.in$ va contine numerele $N,M,R,C$ reprezetand dimensiunea matricii $A$ si limitele inferioare ale dimensiunilor submatricii cerute. Urmatoarele $N$ linii vor contine cate $M$ numere naturale.
 
h2. Date de Iesire
 
Fiserul $balans.out$ va contine pe o singura linie o valoare reprezentand balansul maxim posibil al unei submatrici. Rezultatul va fi afisat cu 3 zecimale exacte.
 
h2. Restrictii si observatii
 
* $1 ≤ N, M ≤ 150$
* $0 ≤ R ≤ N$
* $0 ≤ C ≤ M$
* $0 ≤ A{~i,j~} ≤ 100.000$
 
h2. Exemplu
 
table(example). |_. balans.in |_. balans.out |
| 3 4 2 1
 15 5 15 8
 1 2 1 3
 4 8 8 4 | 11.500 |
 
h3. Explicatie
 
Se permuta circular odata randurile si se obtine matricea:
{$1  2 1  3$}
{$4  8 *8*  4$}
{$15 5 *15* 8$}
Submatricea de balans maxim este ingrosata.
 
 
==Include(page="template/taskfooter" task_id="balans")==

Submatricea de balans maxim este ingrosata.
==Include(page="template/taskfooter" task_id="balans")==

642