Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2015-07-25 21:31:59.
Revizia anterioară   Revizia următoare  

 

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 ca toata lumea s-a jucat Rayman si ii cunoaste protagonistul.
Au aparut noi plansi in renumitul joc si voi aveti datoria de ai 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 plansa 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 reusit sa puna la capat o potiune care sa-i alunge puterea de a zbura lui Rayman, 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 navale pe el si o sa-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. 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 trece 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 si cu gradul total de risc minim. 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 care spune ca 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 plansile.

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.

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.

Restricţii

• 1<=N<=15
• 1<=M<=100000
• 1<=inaltimea unui munte<=1000000
• 0<=riscul asumat travesrsarii unui obstacol<=10^9
• 0<= energia consumata pentru o saritura<=1000
• E[i][i]=0, 1<=i<=N

Pentru 10 puncte:
• 1<=M<=1000
• E[i][j]=0, 1<=i<=N, 1<=j<=N

Pentru 20 puncte:
• 1<=N<=8
• 1<=M<=1000

Pentru 30 puncte:
• E[i][j]=0, 1<=i<=N, 1<=j<=N

Pentru 40 puncte:
• Restrictiile initiale

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?