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

Gigel este un mare amator de excursii la munte. In acelasi timp este si un bun informatician. El a observat ca facand un traseu intre doua obiective turistice oboseste mai putin decat daca alege un alt traseu intre aceleasi obiective. Gigel si-a propus sa gaseasca un model care sa-i permita determinarea unui traseu pe care, daca-l alege, va ajunge la destinatie cat mai putin obosit. Astfel, el reprezinta terenul in care se afla cele doua obiective turistice printr-un tablou bidimensional cu $n$ linii (numerotate de la $1$ la {$n$}) si $m$ coloane (numerotate de la {$1$} la {$m$}), cu elemente numere naturale strict pozitive, in care fiecare element reprezinta cota unei zone de teren de forma unui patrat cu latura $1$ m. Efortul pe care-l face pentru a trece dintr-o zona cu cota {$c{~1~}$} intr-o zona vecina cu o cota mai inalta ({$c{~2~}$}) se calculeaza dupa cum urmeaza. Se traseaza un triunghi dreptunghic ca in figura:
 
!>problema/excursie?excursie.gif!
 
* {$c{~1~}$} si {$c{~2~}$} sunt cele doua cote {$c{~1~}$} < {$c{~2~}$}
* $1$ distanta dintre centrele celor doua zone vecine
* $&#0945;$ este unghiul pantei care trebuie urcata
* <tex> d = \sqrt{(c_{2}-c_{1})^{2} + 1 } </tex>

Gigel este un mare amator de excursii la munte. In acelasi timp este si un bun informatician. El a observat ca facand un traseu între doua obiective turistice oboseste mai putin decat daca alege un alt traseu între aceleasi obiective. Gigel si-a propus sa gaseasca un model care sa-i permita determinarea unui traseu pe care, daca-l alege, va ajunge la destinatie cat mai putin obosit. Astfel, el reprezinta terenul în care se afla cele doua obiective turistice printr-un tablou bidimensional cu n linii (numerotate de la 1 la n) si m coloane (numerotate de la 1 la m), cu elemente numere naturale strict pozitive, în care fiecare element reprezinta cota unei zone de teren de forma unui patrat cu latura 1 m. Efortul pe care-l face pentru a trece dintr-o zona cu cota c1 într-o zona vecina cu o cota mai înalta (c2) se calculeaza dupa cum urmeaza. Se traseaza un triunghi dreptunghic ca în figura:

Apoi calculeaza efortul astfel:

{$ef = d * tg α$}
 
table{width:10%}. | 10 | 6 |
| 1
| 2
|
 
In exemplul urmator consideram patru zone vecine avand cotele {$1$}, {$2$}, {$6$}, {$10$}. Pentru a ajunge din zona de cota $1$ in zona de cota $10$ se pot alege doua trasee:

$ef = d * tg α$
In exemplul urmator consideram patru zone vecine avand cotele {$1$}, {$2$}, {$6$}, {$10$}. Pentru a ajunge din zona de cota $1$ în zona de cota $10$ se pot alege doua trasee:

# direct, ceea ce presupune un efort calculat astfel:

$ef = d * tg α = √82 * 9 ≈ 81$

$ef = d * tg α = ??? * 9 ??? 81$

# ocolit, prin zonele de cote $2$ si {$6$}, ceea ce presupune un efort calculat astfel:

$ef = ef{~1~}+ef{~2~}+ef{~3~} = √2 + √17 * 4 + √17 * 4 ≈ 34$

$ef = ef{~1~}+ef{~2~}+ef{~3~} = ??? + ??? * 4 + ??? * 4 ≈ 34$

Efortul pe care-l face pentru a trece dintr-o zona avand cota $c{~1~}$ intr-o zona vecina cu aceeasi cota este {$1$}.
Efortul pe care-l face pentru a trece dintr-o zona avand cota $c{~1~}$ intr-o zona vecina cu o cota mai joasa ({$c{~2~}$}) este jumatate din efortul pe care l-ar face la urcare (adica de la cota $c{~2~}$ la cota {$c{~1~}$}).

Efortul pe care-l face pentru a trece dintr-o zona avand cota $c{~1~}$ într-o zona vecina cu aceeasi cota este {$1$}.
Efortul pe care-l face pentru a trece dintr-o zona avand cota $c{~1~}$ într-o zona vecina cu o cota mai joasa ({$c{~2~}$}) este jumatate din efortul pe care l-ar face la urcare (adica de la cota $c{~2~}$ la cota {$c{~1~}$}).

h2. Cerinta

Scrieti un program care sa determine efortul minim pentru a ajunge de la un obiectiv turistic la altul. Daca exista mai multe trasee cu acelasi efort minim se va alege cel care are lungimea cea mai mica. In cazul in care aceasta lungime depaseste valoarea {$Lmax$} se va afisa {$-1$}.

Scrieti un program care sa determine efortul minim pentru a ajunge de la un obiectiv turistic la altul, lungimea traseului nedepasind o valoare data {$Lmax$}.

h2. Date de intrare
Fisierul de intrare $excursie.in$ contine:

* pe prima linie doua numere naturale $n$ si $m$ separate printr-un spatiu, reprezentand dimensiunile terenului;

* pe linia a doua numarul real $Lmax$ reprezentand lungimea maxima admisa a drumului;
* urmatoarele $n$ linii contin fiecare cate $m$ valori naturale, separate prin, reprezentand in ordine cotele zonelor de teren;

* pe linia a doua numarul real Lmax reprezentand lungimea maxima admisa a drumului;
* urmatoarele $n$ linii contin fiecare cate $m$ valori naturale, separate prin, reprezentand în ordine cotele zonelor de teren;

* ultima linie contine patru valori naturale $li$ $ci$ $lf$ {$cf$}, separate prin cate un spatiu, unde {$li$}, $ci$ reprezinta linia si respectiv coloana punctului de plecare, iar $lf$ $cf$ reprezinta linia si respectiv coloana punctului de sosire.
h2. Date de iesire

Fisierul de iesire $excursie.out$ va contine pe prima linie doua numere reale separate printr-un spatiu {$ef d$}, reprezentand efortul minim depus pentru a ajunge de la un obiectiv la altul si respectiv lungimea minima a unui drum parcurs cu efort minim. Rezultatele vor fi afisate cu cate trei zecimale.

Fisierul de iesire $excursie.out$ va contine pe prima linie doua numere reale separate printr-un spatiu ef d, reprezentand efortul minim depus pentru a ajunge de la un obiectiv la altul si respectiv lungimea minima a unui drum parcurs cu efort minim. Rezultatele vor fi afisate cu cate trei zecimale.

h2. Restrictii
* $2 ≤ n, m ≤ 50$

* Deplasarea dintr-o zona in alta se poate face doar in $4$ directii: (N, E, S, V). Mai exact, daca pozitia curenta este pe linia {$i$}, coloana {$j$}, prin deplasare la N se trece in pozitia ({$i-1,j$}), la E in ({$i,j+1$}), la S in ({$i+1,j$}), iar la V in ({$i, j-1$}). (daca aceste pozitii exista).
* Cotele sunt numere naturale cu valori intre $1$ si {$100$}.

* Deplasarea dintr-o zona în alta se poate face doar în $4$ directii: (N, E, S, V). Mai exact, daca pozitia curenta este pe linia {$i$}, coloana {$j$}, prin deplasare la N se trece în pozitia ({$i-1,j$}), la E în ({$i,j+1$}), la S în ({$i+1,j$}), iar la V în ({$i, j-1$}). (daca aceste pozitii exista).
* Cotele sunt numere naturale cu valori între $1$ si {$100$}.

* Se recomanda utilizarea tipurilor reale pe $64$ biti. Rezultatul va fi considerat corect daca diferenta absoluta dintre rezultatul afisat si rezultatul corect este < $0.01$
* Se acorda $60%$ din punctaj pentru determinarea corecta a efortului minim, respectiv $100%$ pentru rezolvarea corecta a ambelor cerinte.

h3. Explicatie

{$√2 + √17 * 8 = 34.399 (1.41421356+32.98484500=34.39905856)$}
{$√2 + √17 * 2 = 9.660  (1.41421356+ 8.24621125= 9.66042481)$}

{$??? + ??? * 8 = 34.399 (1.41421356+32.98484500=34.39905856)$}
{$??? + ??? * 2 = 9.660  (1.41421356+ 8.24621125= 9.66042481)$}

Traseul este corect deoarece lungimea drumului $9.660$ este mai mica decat valoarea data $Lmax = 11$
== include(page="template/taskfooter" task_id="excursie") ==

== SmfTopic(topic_id="...") ==

1836