Fişierul intrare/ieşire:rayman.in, rayman.outSursăJunior Challenge 2015
AutorChichirim GeorgeAdăugată deJuniorChallenge2015JuniorChallenge2016 JuniorChallenge2015
Timp execuţie pe test1.6 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Rayman

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, 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  (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), atunci nu este permis ca b_1 > b_2). 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 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.

Date de intrare

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.

Date de ieşire

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

Restricţii

  • 1 ≤ N ≤ 15
  • 1 ≤ M ≤ 105
  • 1 ≤ înălţimea unui munte ≤ 106
  • 0 ≤ riscul asumat travesrsarii unui obstacol ≤ 109
  • 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.
  • 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

Exemplu

rayman.inrayman.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

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)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?