== include(page="template/taskheader" task_id="bemo") ==
Poveste şi cerinţă...
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$ ...
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
În fişierul de ieşire $bemo.out$ ...
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$
* 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") ==
== include(page="template/taskfooter" task_id="bemo") ==
