== include(page="template/taskheader" task_id="lenes") ==
Poveste şi cerinţă...
_Leneşul este un animal foarte leneş._ El se deplasează numai în linie dreaptă, dar face din când în când câte un popas. În această problemă leneşul trebuie să traverseze de la nord la sud şi înapoi un teren reprezentat de o matrice de dimensiuni *M×N* cu valori numere naturale. Valorile reprezintă efortul cerut pentru traversarea zonei respective. Leneşul va alege o coloană pentru traversarea matricei, iar pentru popasuri, în număr de *k1*, va alege zone alăturate drumului din coloana din stânga sau cea din dreapta. În cazul în care se va întoarce va proceda la fel, dar va face *k2* popasuri. Regulile problemei cer ca cele două drumuri să nu aibă zone comune.
h2. Cerinta
Cunoscând dimensiunile *M, N* ale terenului, numărul de popasuri *k1, k2* şi efortul pentru traversarea fiecărei zone a terenului, să se determine:
*1.* Efortul minim de parcurgere a terenului de la *Nord la Sud*, folosind *k1* popasuri.
*2.* Efortul minim de parcurgere a terenului de la *Nord la Sud* şi înapoi de la *Sud la Nord*, folosind *k1* popasuri la deplasarea *Nord - Sud*, respectiv *k2* popasuri la deplasarea *Sud - Nord*.
h2. Date de intrare
Fişierul de intrare $lenes.in$ ...
Fişierul *lenes.in* conţine:
* Pe prima linie un număr natural *p* reprezentând cerinţa de rezolvare. Pentru toate testele de intrare numărul *p* poate avea doar valoarea *1 sau 2*.
* Pe linia a doua sunt 4 numere naturale *M, N, k1, k2*, separate prin câte un spaţiu cu semnificaţia de mai sus.
* Pe următoarele *M* linii se găsesc câte *N* numere naturale separate prin câte un spaţiu, reprezentând eforturile de traversare a fiecărei zone a terenului.
h2. Date de ieşire
În fişierul de ieşire $lenes.out$ ...
* Dacă valoarea lui $p$ este $1$, *se va rezolva numai cerinţa 1*. În acest caz fişierul *lenes.out* va conţine un singur număr natural reprezentând efortul minim necesar pentru traversarea terenului în condiţiile date de la *Nord la Sud*.
* Dacă valoarea lui $p$ este $2$, *se va rezolva numai cerinţa 2*. În acest caz fişierul *lenes.out* va conţine un singur număr natural reprezentând efortul minim necesar pentru traversarea terenului în condiţiile date în ambele sensuri de la *Nord la Sud* şi de la *Sud la Nord*.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $3 ≤ M, N ≤ 500$
* $0 ≤ k1, k2 ≤ M$
* Valorile din matrice sunt numere naturale din intervalul $[1, 1000].$
* _Leneşul_ poate să facă popasuri pe aceeaşi linie în *ambele* celule din stânga şi din dreapta coloanei parcurse.
* Deplasarea între ultima zonă a drumului parcurs de la Nord la Sud şi prima zonă a drumului parcurs de la Sud la Nord la întoarcere se face cu efort $0$.
h2. Exemplu
table(example). |_. lenes.in |_. lenes.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
table(example). |_. lenes.in |_. lenes.out |_. Explicatie |
| 1
4 7 2 3
99 1 33 9 2 4 7
99 1 44 8 1 2 3
98 1 55 8 2 3 2
97 1 66 4 3 2 1
| 12
| p = 1
Leneşul traversează terenul de la Nord la Sud pe
coloana a 5-a cu popas în zonele (2, 6) şi (4, 6).
*Atenţie! Pentru acest test se rezolvă doar cerinţa 1.*
|
|2
4 7 3 2
99 1 33 9 2 4 7
99 1 44 8 1 2 3
98 1 55 8 2 2 2
97 1 66 4 3 2 1
|35
|p = 2
Leneşul traversează terenul de la Nord la Sud pe
coloana a 7-a cu popasuri în zonele (3, 6), (1, 6), (4,
6), iar de la Sud la Nord pe coloana a 5 - a, cu popas
în zonele (4, 4) şi (2, 6).
*Atenţie! Pentru acest test se rezolvă doar cerinţa 2.*
|
|2
3 7 2 2
2 1 33 9 99 4 7
1 1 44 9 99 2 3
2 1 55 9 99 2 2
|19
|p = 2
Leneşul traversează terenul de la Nord la Sud pe
coloana a 6-a cu popasuri în zonele (2, 7), (3, 7), iar
de la Sud la Nord pe coloana a 2 - a, cu popasuri în
zonele (3, 1) şi (2, 1). Efortul de deplasare între
zonele (3, 6) şi (3, 2) este nul.
*Atenţie! Pentru acest test se rezolvă doar cerinţa 2.*
|
...
== include(page="template/taskfooter" task_id="lenes") ==
