Diferente pentru problema/balans intre reviziile #1 si #2
Diferente intre titluri:
Balans
balans
Diferente intre continut:
==Include(page="template/taskheader" task_id="balans")==
== include(page="template/taskheader" task_id="balans") == Poveste ... h2. Cerinta ... h2. Restrictii ... h2. Date de intrare ... h2. Date de iesire ... h2. Exemplu | balans.in | balans.out | | linia1 linia2 linia3 | linia1 linia2 | == include(page="template/taskfooter" 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 Submatricea de balans maxim este ingrosata. ==Include(page="template/taskfooter" task_id="balans")==