== include(page="template/taskheader" task_id="bemo") ==
Se dă o matrice cu R linii şi C coloane de numere distincte de la 1 la R*C. Bemo, personajul emoţional, doreşte să urmărească cel mai bun drum din colţul superior stânga, de coordonate (1, 1), în colţul inferior dreapta, de coordonate (R, C). Un drum este o secvenţă de numere din matrice în care fiecare număr se găseşte în jos sau la dreapta numărului anterior, i.e. dacă (i, j) este poziţia unui număr de pe un drum, atunci următorul număr poate fi cel de pe poziţia (i+1, j) sau cel de pe poziţia (i, j+1). Pentru a determina dacă un drum A este mai bun decât un drum B, numerele fiecărui drum se vor sorta şi se va alege cel mai mic lexicografic, e.g. [1,3,5,6,8] < [1,4,5,6,7].
Se dă o matrice cu $R$ linii şi $C$ coloane de numere distincte de la $1$ la $R*C$. Bemo, personajul emoţional, doreşte să urmărească cel mai bun drum din colţul superior stânga, de coordonate $(1, 1)$, în colţul inferior dreapta, de coordonate $(R, C)$. Un drum este o secvenţă de numere din matrice în care fiecare număr se găseşte în jos sau la dreapta numărului anterior, i.e. dacă $(i, j)$ este poziţia unui număr de pe un drum, atunci următorul număr poate fi cel de pe poziţia $(i+1, j)$ sau cel de pe poziţia $(i, j+1)$. Pentru a determina dacă un drum A este mai bun decât un drum B, numerele fiecărui drum se vor sorta şi se va alege cel mai mic lexicografic, e.g. $[1,3,5,6,8] < [1,4,5,6,7]$.
h2. Date de intrare
Fişierul de intrare bemo.in conţine pe prima linie două numere naturale R i ş C, unde R este numărul liniilor, iar C numărul coloanelor matricei lui Bemo. Pe următoarele R linii se vor găsi câte C numere separate printr-un spaţiu. Fiecare număr va fi unic şi va fi cuprins în intervalul [1, R*C].
Fişierul de intrare bemo.in conţine pe prima linie două numere naturale $R$ si $C$, unde $R$ este numărul liniilor, iar $C$ numărul coloanelor matricei lui Bemo. Pe următoarele $R$ linii se vor găsi câte $C$ numere separate printr-un spaţiu. Fiecare număr va fi unic şi va fi cuprins în intervalul $[1, R*C]$.
h2. Date de ieşire
Fi ierul de iesire ş bemo.out va con ine ţ R+C-1 numere reprezentând cel mai bun drum pe care Bemo îl poate alege. Numerele vor fi scrise separate printr-un spatiu.
Fisierul de iesire bemo.out va contine $R+C-1$ numere reprezentând cel mai bun drum pe care Bemo îl poate alege. Numerele vor fi scrise separate printr-un spatiu.
h2. Restricţii
* $1$ ≤ $R$, $C$ ≤ $1500$
* Pentru 40% din teste $1$ ≤ $R$, $C$ ≤ $750$
* Pentru 70% din teste $1$ ≤ $R$, $C$ ≤ $1300$
* Pentru $40%$ din teste $1$ ≤ $R$, $C$ ≤ $750$
* Pentru $70%$ din teste $1$ ≤ $R$, $C$ ≤ $1300$
* Spunem că un drum A=(a ~1~,a ~2~,..,a ~R+C-1~) este mai mic lexicografic decât un drum B=(b ~1~, b ~2~,..,b ~R+C-1~) dacă există o poziţie p astfel încât x ~p~ < y ~p~ şi x ~1~ = y ~1~, x ~2~ = y ~2~,..., x ~p-1~ = y ~p-1~.
h2. Exemplu
table(example). |_. bemo.in |_. bemo.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4 4
7 4 13 3
8 11 12 2
10 9 1 5
16 14 15 6
| 7 4 11 9 1 5 6
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="bemo") ==
