== include(page="template/taskheader" task_id="excursie") ==
Poveste si cerinta...
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 α$
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 α = ??? * 9 ??? 81$
# ocolit, prin zonele de cote $2$ si {$6$}, ceea ce presupune un efort calculat astfel:
$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~}$ î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, 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 î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.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $2 ≤ n, m ≤ 50$
* 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.
h2. Exemplu
table(example). |_. excursie.in |_. excursie.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2 2
11
10 6
1 2
2 1 1 1
| 34.399 9.660
|
h3. Explicatie
...
{$??? + ??? * 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") ==
