== include(page="template/taskheader" task_id="parcele1") ==
Poveste şi cerinţă...
Bătrân fiind, ţăranul Florea este nevoit să lase terenul său moştenire celor $P$ fii ai săi. Fiecare fiu are doi copii, nepoţi ai lui Florea. Terenul ţăranului reprezintă o matrice cu $N$ linii şi $M$ coloane numerotate de la $1$ la $N$, respectiv de la $1$ la $M$. Fiecare element al matricei reprezintă câştigul obţinut la cultivarea cu produse agricole. Terenul poate fi împărţit în parcele. Parcela este o succesiune de linii învecinate din matrice. Fiecare parcelă, ce revine unui fiu, trebuie împărţită celor doi nepoţi în loturi. Primul lot este format din primele $K$ coloane ale parcelei, iar al doilea lot din ultimele $M$ - $K$ coloane ale fiecărei parcele. Ţăranul împarte terenul în $P$ parcele, fiecare fiind la rândul ei împărţită în două loturi.
Câştigul unui lot este suma câştigurilor din acea bucată de pământ. Înţeleptul bătrân Florea doreşte să facă o împărţire cât mai echilibrată între nepoţii săi. El doreşte ca suma diferenţelor dintre câştigurile de pe loturile a doi nepoţi, copii ai aceluiaşi fiu, să fie cât mai mică (diferenţa este considerată în modul, deci un număr pozitiv sau nul).
h2. Cerinţă
Dându-se configuraţia terenului ţăranului Florea şi câştigul ce poate fi obţinut la cultivarea cu produse agricole, calculaţi suma cerută şi numărul de posibilităţi de a împărţi terenul astfel încât să se obţină această valoare.
h2. Date de intrare
Fişierul de intrare $parcele1.in$ ...
Pe prima linie a fişierului $parcele1.in$ se află trei numere naturale $N$ $M$ $P$ ( $N$ respectiv $M$ coordonatele terenului ţăranului, $P$ numărul de fii). Următoarele $N$ linii conţin $M$ valori naturale, reprezentând câştigurile obţinute la cultivare.
h2. Date de ieşire
În fişierul de ieşire $parcele1.out$ ...
Prima linie a fişierului $parcele1.out$ va conţine valoarea sumei cerute. Următoarea linie va conţine numărul de posibilităţi pe care le are Florea pentru a realiza împărţirea terenului său astfel încât să asigure acestă valoare minimă.
h2. Restricţii
* $... ≤ ... ≤ ...$
* {$2 < N, M ≤ 20$}
* {$2 ≤ P ≤ N$}
* Câştigul la cultivare este cel mult {$99$}.
* Câştigul total al unui lot nu poate fi nul.
h2. Exemplu
table(example). |_. parcele1.in |_. parcele1.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4 4 3
3 3 4 3
1 4 3 3
2 4 3 4
1 3 2 4
| 5
5
|
h3. Explicaţie
...
Diferenţa minimă este 5. Sunt cinci soluţii de împărţire a terenului, soluţii care sunt ilustrate în continuare.
!problema/parcele1?poza1.bmp!
== include(page="template/taskfooter" task_id="parcele1") ==
