Rayman

rayman

== include(page="template/taskheader" task_id="rayman") ==

!>problema/rayman?img.png!
Cred că toată lumea s-a jucat Rayman şi îi cunoaşte protagonistul.
Au apărut planşe noi în renumitul joc şi voi aveţi datoria de a-i spune lui Rayman pe unde să meargă. O planşă este alcătuită din mai mulţi munţi de diferite înălţimi pe vârful cărora se află câte un obstacol cu un grad de risc anume. Mai exact, planşa arată ca o matrice cu $N$ linii şi $M$ coloane, iar fiecare căsuţă din matrice reprezintă un munte cu obstacolul sau. Deoarece Mister Dark, Admiral Rezorbeard, Andre şi The Magician şi-au unit forţele şi au inventat o poţiune care să-i alunge lui Rayman puterea de a zbura, **acesta poate să sară de pe un munte numai pe altul cu înălţime mai mică sau egală**. Ştim cu toţii că lui Rayman îi place cel mai mult aventura, **aşa că acesta doreşte să treacă prin cât mai multe obstacole**, dar, mai ştim că Rayman este un om superstiţios, deci el nu vrea să se întoarcă din drum (acesta crede că Mister Unlucky o să dea năvală peste el şi o să-l omoare).

Cred ca toata lumea s-a jucat Rayman si ii cunoaste protagonistul.
Au aparut planşe noi in renumitul joc si voi aveti datoria de a-i spune lui Rayman pe unde sa mearga. O plansa este alcatuita din mai multi munti de diferite inaltimi pe varful carora se afla cate un obstacol cu un grad de risc anume. Mai exact, planşa arata ca o matrice cu $N$ linii si $M$ coloane, iar fiecare casuta din matrice reprezinta un munte cu obstacolul sau. Deoarece Mister Dark, Admiral Rezorbeard, Andre si The Magician si-au unit fortele si au inventat o potiune care sa-i alunge lui Rayman puterea de a zbura, **acesta poate sa sara de pe un munte numai pe altul cu inaltime mai mica sau egala**. Stim cu totii ca lui Rayman ii place cel mai mult aventura, **asa ca acesta doreste sa treaca prin cat mai multe obstacole**, dar mai stim ca Rayman este un om superstitios, asa ca el nu vrea sa se intoarca din drum (aceste crede ca Mister Unlucky o sa dea navala peste el si o sa-l omoare).

Mai exact, **dacă la un moment dat el se află pe un munte pe linia $x$ şi coloana $y$ atunci în viitor el poate să ajungă pe un munte de pe linia $x$ şi coloana $y1$ doar dacă $y < y1$** (cu alte cuvinte, dacă înşiruirea de mutări este <tex> (x_1, y_1), (x_2, y_2), .., (x_k, y_k), (a, b_1), (x_{k+1}, y_{k+1}), ..., (x_s, y_s), (a, b_2), (x_{s+1}, y_{s+1}), ..., (x_q, y_q),</tex> atunci nu este permis ca <tex>b_1 > b_2</tex>). Totuşi, noi mai ştim că la cât de neînfricat este Rayman, el nu doreşte să îşi asume foarte multe riscuri, prin urmare voi trebuie să îi alegeţi un drum care **să treacă prin cât mai multe obsacole, dar cu gradul total de risc minim (în caz de egalitate după lungime)**. Pentru că lui nu îi place să piardă timpul alegând din mai multe trasee şi doreşte să plece la drum cât mai repede posibil, **acesta va garantează că există o singură mulţime de obstacole cu cardinal maxim care poate fi parcursă în condiţiile de mai sus, care să aibă un grad total de risc minim (drumul propriu-zis nefiind neapărat unic)**.

Mai exact, **daca la un moment dat el se afla pe un munte pe linia $x$ si coloana $y$ atunci in viitor el poate sa ajunga pe un munte de pe linia $x$ si coloana $y1$ doar daca $y < y1$** (cu alte cuvinte, daca insiruirea de mutari este <tex> (x_1,y_1), (x_2,y_2),.., (x_k,y_k), (a,b_1), (x_{k+1},y_{k+1}),..., (x_s,y_s), (a,b_2), (x_{s+1},y_{s+1}),..., (x_q,y_q)</tex>, atunci nu este permis ca <tex>b_1 > b_2</tex>). Totusi, noi mai stim ca la cat de neinfricat este Rayman, el nu doreste sa isi asume foarte multe riscuri, asa ca voi trebuie sa ii alegeti un drum care **sa treaca prin cat mai multe obsacole, dar cu gradul total de risc minim (in caz de egalitate dupa lungime)**. Pentru ca lui nu ii place sa piarda timpul alegand din mai multe trasee si doreste sa plece la drum cat mai repede posibil, **acesta va garanteaza ca exista o singura multime de obstacole cu cardinal maxim care poate fi parcursa in conditiile de mai sus, care sa aiba un grad total de risc minim (drumul propriu-zis nefiind neaparat unic)**.

Dar pentru că jocul a evoluat destul de mult de la prima apariţie din $1995$, şi pentru că suntem în anul $2015$, şi pentru că am reuşit să scăpăm cu bine de anul $2013$, există un coeficient de energie, şi anume: fie matrice pătratică $E$ de dimensiune $N$ cu semnificaţia **$E[i][j]$ este energia consumată pentru a sări de pe un munte care se află pe linia $i$ pe un munte care se află pe linia $j$. Dar toată lumea ştie că Rayman poate să sară foarte mult şi energia consumată pentru o săritură nu depinde de lungimea săriturii cât depinde de săritura propriu-zisă, aşa că el consumă mai multă energie dacă sare printr-o piatră intermediară, cu alte cuvinte se garanteaza că $E[i][j] ≤ E[i][k] + E[k][j]$, oricare ar fi $k$**. Bineînţeles, Rayman vrea să aibe cât mai multă energie pentru obstacole, aşa că voi trebuie să-i alegeţi **un drum care să consume şi cât mai puţină energie, în caz că există mai multe cu acelaşi cardinal şi grad total de risc. Rayman poate să înceapă de oriunde**.
Rayman o să va răsplătească cu $100$ de puncte dacă îl ajutaţi să treacă de toate planşele.

Dar pentru ca jocul a evoluat destul de mult de la prima aparitie din $1995$, si pentru ca suntem in anul $2015$, si pentru ca am reusit sa scapam cu bine de anul 2013, exista un coeficient de energie, si anume: fie matrice patratica $E$ de dimensiune $N$ cu semnificatia **$E[i][j]$ este energia consumata pentru a sari de pe un munte care se afla pe linia $i$ pe un munte care se afla pe linia $j$**. Bineinteles, Rayman vrea sa aibe cat mai multa energie pentru obstacole asa ca voi trebuie sa-i alegeti **un drum care sa consume si cat mai putina energie, in caz ca exista mai multe cu acelasi cardinal si grad total de risc. Rayman poate sa inceapa de oriunde**.
Rayman o sa va rasplateasca cu $100$ de puncte daca il ajutati sa treaca de toate planşele.
h2. Date de intrare

h2. Date de intrare

Pe prima linie a fisierului $rayman.in$ se afla douna numere natural $N$ si $M$ cu semnificatiile de mai sus. Pe urmatoarele $N$ linii se afla cate $M$ numere care reprezinta inaltimile muntilor. Fisierul de intrare mai contine inca $N$ linii a cate $M$ numere care reprezinta gradul de risc al obstacolelor. Pe urmatoarele $N$ linii se afla cate $N$ numere care reprezinta matricea $E$.

Pe prima linie a fişierului $rayman.in$ se află două numere natural $N$ şi $M$ cu semnificaţiile de mai sus. Pe următoarele $N$ linii se află câte $M$ numere care reprezintă înălţimile munţilor. Fişierul de intrare mai conţine încă $N$ linii a câte $M$ numere care reprezintă gradul de risc al obstacolelor. Pe următoarele $N$ linii se află câte $N$ numere care reprezintă matricea $E$.

h2. Date de ieşire

h2. Date de ieşire

In fisierul $rayman.out$ trebuie sa se afle $3$ numere $Nrmax$, $Riscmin$ si $Energmin$ despartite prin cate un spatiu. $Nrmax$ reprezinta numarul maxim de obstacole, $Riscmin$ reprezinta riscul minim asumat pentru a parcurge $Nrmax$ obstacole, iar $Energmin$ este energia minima consumata pentru a parcurge $Nrmax$ obstacole cu gradul de risc $Riscmin$.

În fişierul $rayman.out$ trebuie să se afle $3$ numere $Nrmax$, $Riscmin$ şi $Energmin$ despărţite prin câte un spaţiu. $Nrmax$ reprezintă numărul maxim de obstacole, $Riscmin$ reprezintă riscul minim asumat pentru a parcurge $Nrmax$ obstacole, iar $Energmin$ este energia minimă consumată pentru a parcurge $Nrmax$ obstacole cu gradul de risc $Riscmin$.

h2. Restricţii

h2. Restricţii

*       $1 ≤ N ≤ 15$
*       $1 ≤ M ≤ 10^5^$
*       $1 ≤ inaltimea unui munte ≤ 10^6^$
*       $0 ≤ riscul asumat travesrsarii unui obstacol ≤ 10^9^$
*       $0 ≤ energia consumata pentru o saritura ≤ 1000$
*       $E[i][i] = 0, pentru 1 ≤ i ≤ N$

* $1 ≤ N ≤ 15$
* $1 ≤ M ≤ 10^5^$
* $1 ≤ înălţimea unui munte ≤ 10^6^$
* $0 ≤ riscul asumat travesrsarii unui obstacol ≤ 10^9^$
* $0 ≤ energia consumată pentru o săritură ≤ 1000$
* $E[i][i] = 0, pentru 1 ≤ i ≤ N$

* **Atenţie!** Volum mare de date de intrare, vă recomandăm să optimizaţi citirea folosindu-va de "acest cod":http://pastebin.com/dfEATDDB.

* **Atenţie!** Volum mare de date de intrare, vă recomandăm să optimizaţi citirea folosindu-vă de "acest cod":http://pastebin.com/dfEATDDB.

* **Full feedback!**

* **Full feedback!**

* **Subtask 1 (15 puncte)**:
   •    $1 ≤ M ≤ 1000$
   •    inaltimile muntilor sunt numere distincte doua cate doua

* **Subtask 1 (15 puncte)**:
• $1 ≤ M ≤ 1000$
• înălţimile munţilor sunt numere distincte două câte două

* **Subtask 2 (20 puncte)**:
   •    $1 ≤ N ≤ 8$
   •    $1 ≤ M ≤ 1000$

* **Subtask 2 (20 puncte)**:
• $1 ≤ N ≤ 8$
• $1 ≤ M ≤ 1000$

* **Subtask 3 (25 puncte)**:
   •    $E[i][j] = 0, 1 ≤ i ≤ N, 1 ≤ j ≤ N$

* **Subtask 3 (25 puncte)**:
• $E[i][j] = 0, 1 ≤ i ≤ N, 1 ≤ j ≤ N$

* **Subtask 4 (40 puncte)**:
   •    Restrictiile initiale

* **Subtask 4 (40 puncte)**:
• Restricţiile iniţiale

h2. Exemplu

h2. Exemplu
 
table(example). |_. rayman.in |_. rayman.out |
| 3 8
3 2 4 6 2 1 4 2
5 8 7 6 11 4 9 10
1 1 14 12 5 8 10 20
1 1 5 4 1 1 4 6
5 1 2 1 6 1 8 10
3 3 1 1 1 2 3 2
0 1 2
3 0 2
2 1 0
|11 12 7

table(example). |_. rayman.in |_. rayman.out |
| 3 8
3 2 4 6 2 1 4 2
5 8 7 6 11 4 9 10
1 1 14 12 5 8 10 20
1 1 5 4 1 1 4 6
5 1 2 1 6 1 8 10
3 3 1 1 1 2 3 2
0 1 2
3 0 2
2 1 0
|11 12 7

|

h3. Explicaţie

h3. Explicaţie

Traseul pe care îl urmează Rayman este: $(3, 3) -> (3, 4) -> (2, 2) -> (2, 3) -> (2, 4) -> (3, 5) -> (2, 6) -> (1, 1) -> (1, 2) -> (1, 5) -> (1, 6)$

Traseul pe care il urmeaza Rayman este: $(3, 3) -> (3, 4) -> (2, 2) -> (2, 3) -> (2, 4) -> (3, 5) -> (2, 6) -> (1, 1) -> (1, 2) -> (1, 5) -> (1, 6)$

== include(page="template/taskfooter" task_id="rayman") ==

== include(page="template/taskfooter" task_id="rayman") ==