Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | munte2.in, munte2.out | Sursă | ONI 2003, clasa 10 |
| Autor | Mihai Stroe | Adăugată de |  Tabara Mihai •Tabara |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Munte2
Într-o zonă montană se doreşte deschiderea unui lanţ de telecabine. Staţiile de telecabine pot fi înfiinţate pe oricare din cele N vârfuri ale zonei montane. Vârfurile sunt date în ordine de la stânga la dreapta şi numerotate de la 1 la N, fiecare vârf i fiind precizat prin coordonata X[i] pe axa OX şi prin înălţimea H[i].
Se vor înfiinţa exact K staţii de telecabine. Staţia de telecabine i (2 ≤ i ≤ K) va fi conectată cu staţiile i-1 şi i+1; staţia 1 va fi conectată doar cu staţia 2, iar staţia K, doar cu staţia K-1. Staţia 1 va fi obligatoriu amplasată în vârful 1, iar staţia K în vârful N.
Se doreşte ca lanţul de telecabine să asigure legătura între vârful 1 şi vârful N. Mai mult, se doreşte ca lungimea totală a cablurilor folosite pentru conectare să fie minimă. Lungimea cablului folosit pentru a conecta două staţii este egală cu distanţa dintre ele. În plus, un cablu care uneşte două staţii consecutive nu poate avea lungimea mai mare decât o lungime fixată L.
O restricţie suplimentară este introdusă de formele de relief. Astfel, vârfurile i şi j (i < j) nu pot fi conectate direct dacă există un vârf v ( i < v < j ) astfel încât segmentul de dreapta care ar uni vârfurile i şi j nu ar trece pe deasupra vârfului v. În cazul în care cele trei vârfuri sunt coliniare, se consideră toate trei ca fiind staţii, chiar dacă distanţa dintre vârfurile i şi j este mai mică decât L.
Date de intrare
...
Date de iesire
...
Restrictii
- ... ≤ ... ≤ ...
Exemplu
| munte2.in | munte2.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicatie
...
