rayman

Rayman

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

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

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

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

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

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: **avem o 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. Rayman poate sa inceapa de oriunde**.
Rayman o sa va rasplateasca cu 100 de puncte daca il ajutati sa treaca de toate planşele.

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.

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

h2. Date de intrare

h2. Date de ieşire

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

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

h2. Date de ieşire

h2. Restricţii

Î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$.

*       $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$

h2. Restricţii

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

* $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$

* **Full feedback!**

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

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

* **Full feedback!**

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

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

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

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

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

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

h2. Exemplu

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

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

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

|

h3. Explicaţie

h3. Explicaţie

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

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

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

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