Fişierul intrare/ieşire:parcele1.in, parcele1.outSursăONI 2009, clasa a 8-a
AutorClaudia PuiaAdăugată deandrici_cezarAndrici Cezar andrici_cezar
Timp execuţie pe test0.1 secLimită de memorie4736 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Parcele1

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).

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.

Date de intrare

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.

Date de ieşire

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ă.

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.

Exemplu

parcele1.inparcele1.out
4 4 3
3 3 4 3
1 4 3 3
2 4 3 4
1 3 2 4
5
5

Explicaţie

Diferenţa minimă este 5. Sunt cinci soluţii de împărţire a terenului, soluţii care sunt ilustrate în continuare.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content