Fişierul intrare/ieşire:excursie.in, excursie.outSursăONI 2007, clasa 10
AutorMarinel SerbanAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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 c1 intr-o zona vecina cu o cota mai inalta (c2) se calculeaza dupa cum urmeaza. Se traseaza un triunghi dreptunghic ca in figura:

  • c1 si c2 sunt cele doua cote c1 < c2
  • 1 distanta dintre centrele celor doua zone vecine
  • α este unghiul pantei care trebuie urcata
  •  d = \sqrt{(c_{2}-c_{1})^{2} + 1 }

Apoi calculeaza efortul astfel:
ef = d * tg α

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

  1. direct, ceea ce presupune un efort calculat astfel:
    ef = d * tg α = √82 * 9 ≈ 81
  2. ocolit, prin zonele de cote 2 si 6, ceea ce presupune un efort calculat astfel:
    ef = ef1+ef2+ef3 = √2 + √17 * 4 + √17 * 4 ≈ 34

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

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.

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;
  • 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.

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.

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

Exemplu

excursie.inexcursie.out
2 2
11
10 6
1 2
2 1 1 1
34.399 9.660

Explicatie

√2 + √17 * 8 = 34.399 (1.41421356+32.98484500=34.39905856)
√2 + √17 * 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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content