Gigel este un mare amator de excursii la munte. În acelaşi timp este şi un bun informatician. El a observat că făcând un traseu între două obiective turistice oboseşte mai puţin decât dacă alege un alt traseu între aceleaşi obiective. Gigel şi-a propus să găsească un model care să-i permită determinarea unui traseu pe care, dacă-l alege, va ajunge la destinaţie cât mai puţin obosit. Astfel, el reprezintă terenul în care se află cele două obiective turistice printr-un tablou bidimensional cu n linii (numerotate de la 1 la n) şi m coloane (numerotate de la 1 la m), cu elemente numere naturale strict pozitive, în care fiecare element reprezintă cota unei zone de teren de forma unui pătrat cu latura 1 m. Efortul pe care-l face pentru a trece dintr-o zonă cu cota c1 într-o zonă vecină cu o cotă mai înaltă (c2) se calculează după cum urmează. Se trasează un triunghi dreptunghic ca în figură:
Apoi calculează efortul astfel:
ef = d * tg α
În exemplul următor considerăm patru zone vecine având cotele 1, 2, 6, 10.
Pentru a ajunge din zona de cotă 1 în zona de cotă 10 se pot alege două trasee:
1. direct, ceea ce presupune un efort calculat astfel: ef = d * tg α = R(82) * 9 ≈ 81, unde R(82) este Radical din 82
2. ocolit, prin zonele de cote 2 şi 6, ceea ce presupune un efort calculat astfel: ef = ef1+ef2+ef3 = R(2) + R(17) * 4 + R(17) * 4 ≈ 34
Efortul pe care-l face pentru a trece dintr-o zonă având cota c1 într-o zonă vecină cu aceeaşi cotă este 1.
Efortul pe care-l face pentru a trece dintr-o zonă având cota c1 într-o zonă vecină cu o cotă mai joasă (c2) este jumătate din efortul pe care l-ar face la urcare (adică de la cota c2 la cota c1).
Cerinţă
Scrieţi un program care să determine efortul minim pentru a ajunge de la un obiectiv turistic la altul, lungimea traseului nedepăşind o valoare dată Lmax.
Date de intrare
Fişierul de intrare excursia.in conţine:
– pe prima linie două numere naturale n şi m separate printr-un spaţiu, reprezentând dimensiunile terenului;
– pe linia a doua numărul real Lmax reprezentând lungimea maximă admisă a drumului;
– următoarele n linii conţin fiecare câte m valori naturale, separate prin spaţiu, reprezentând în ordine cotele zonelor de teren;
– ultima linie conţine patru valori naturale li ci lf cf, separate prin câte un spaţiu, unde li, ci reprezintă linia şi respectiv coloana punctului de plecare, iar lf cf reprezintă linia şi respectiv coloana punctului de sosire.
Date de ieşire
Fişierul de ieşire excursia.out va conţine pe prima linie două numere reale separate printr-un spaţiu ef d, reprezentând efortul minim depus pentru a ajunge de la un obiectiv la altul şi respectiv lungimea minimă a unui drum parcurs cu efort minim. Rezultatele vor fi afişate cu câte trei zecimale.
Restricţii
• 2 ≤ n, m ≤ 50
• Deplasarea dintr-o zonă în alta se poate face doar în 4 direcţii: (N, E, S, V). Mai exact, dacă poziţia curentă este pe linia i, coloana j, prin deplasare la N se trece în poziţia (i-1,j), la E în (i,j+1), la S în (i+1,j), iar la V în (i, j-1). (dacă aceste poziţii există).
• Cotele sunt numere naturale cu valori între 1 şi 100.
• Se recomandă utilizarea tipurilor reale pe 64 biţi. Rezultatul va fi considerat corect dacă diferenţa absolută dintre rezultatul afişat şi rezultatul corect este < 0.01
• Se acordă 60% din punctaj pentru determinarea corectă a efortului minim, respectiv 100% pentru rezolvarea corectă a ambelor cerinţe.
Exemple
excursia.in
excursia.out
Explicaţii
2 2
11
10 6
1 2
2 1 1 1
34.399 9.660
R(2) + R(17) * 8 = 34.399 (1.41421356+32.98484500=34.39905856)
R(2) + R(17) * 2 = 9.660 (1.41421356+ 8.24621125= 9.66042481)
Traseul este corect deoarece lungimea drumului 9.660 este mai mică decât valoarea dată Lmax = 11
