Diferente pentru problema/rayman intre reviziile #14 si #77

Diferente intre titluri:

rayman
Rayman

Diferente intre continut:

== include(page="template/taskheader" task_id="rayman") ==
Cred ca toata lumea s-a jucat Rayman si ii cunoaste protagonistul.
Au aparut noi planse 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 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).
!>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 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**.
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ă ai 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$ 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.
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 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$.
 
h2. 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
 
Va rugam sa folositi urmatoarea secventa pentru a citi datele de intare:
== code(cpp)|
class InputReader {
    public:
        InputReader() {}
        InputReader(const char *file_name) {
            input_file = fopen(file_name, "r");
            cursor = 0;
            fread(buffer, SIZE, 1, input_file);
        }
        inline InputReader &operator >>(int &n) {
            while(buffer[cursor] < '0' || buffer[cursor] > '9') {
                advance();
            }
            n = 0;
            while('0' <= buffer[cursor] && buffer[cursor] <= '9') {
                n = n * 10 + buffer[cursor] - '0';
                advance();
            }
            return *this;
        }
    private:
        FILE *input_file;
        static const int SIZE = 1 << 17;
        int cursor;
        char buffer[SIZE];
        inline void advance() {
            ++ cursor;
            if(cursor == SIZE) {
                cursor = 0;
                fread(buffer, SIZE, 1, input_file);
            }
        }
};
 
int main()
{
    InputReader cin("rayman.in");
    int n,m;
    cin>>n>>m;
    //afisarea se face normal
}
==
 
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
h2. 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$.
 
h2. 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$.
 
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 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") ==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.