== include(page="template/taskheader" task_id="rayman") ==
Poveste şi cerinţă...
!>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).
h2. Date de intrare
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)**.
Fişierul de intrare $rayman.in$ ...
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 ieşire
În fişierul de ieşire $rayman.out$ ...
h2. Date de intrare
h2. Restricţii
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. Exemplu
Î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$.
table(example). |_. rayman.in |_. rayman.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
h2. Restricţii
* $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-vă de "acest cod":http://pastebin.com/dfEATDDB.
* **Full feedback!**
* **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 3 (25 puncte)**:
• $E[i][j] = 0, 1 ≤ i ≤ N, 1 ≤ j ≤ N$
* **Subtask 4 (40 puncte)**:
• Restricţiile iniţiale
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 î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") ==
