Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-04-28 13:06:01.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:munte2.in, munte2.outSursăONI 2003, clasa 10
AutorMihai StroeAdăugată deTabaraTabara Mihai Tabara
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Munte2

Intr-o zona montana se doreste deschiderea unui lant de telecabine. Statiile de telecabine pot fi infiintate pe oricare din cele N varfuri ale zonei montane. Varfurile sunt date in ordine de la stanga la dreapta si numerotate de la 1 la N, fiecare varf i fiind precizat prin coordonata Xi pe axa OX si prin inaltimea Hi.
Se vor infiinta exact K statii de telecabine. Statia de telecabine i (2 ≤ iK) va fi conectata cu statiile i - 1 si i + 1; statia 1 va fi conectata doar cu statia 2, iar statia K, doar cu statia K - 1. Statia 1 va fi obligatoriu amplasata in varful 1, iar statia K in varful N.
Se doreste ca lantul de telecabine sa asigure legatura intre varful 1 si varful N. Mai mult, se doreste ca lungimea totala a cablurilor folosite pentru conectare sa fie minima. Lungimea cablului folosit pentru a conecta doua statii este egala cu distanta dintre ele. In plus, un cablu care uneste doua statii consecutive nu poate avea lungimea mai mare decat o lungime fixata L.
O restrictie suplimentara este introdusa de formele de relief. Astfel, varfurile i si j ( i < j) nu pot fi conectate direct daca exista un varf v ( i < v < j) astfel incat segmentul de dreapta care ar uni varfurile i si j nu ar trece pe deasupra varfului v. In cazul in care cele trei varfuri sunt coliniare, se considera toate trei ca fiind statii, chiar daca distanta dintre varfurile i si j este mai mica decat L.

Cerinta

Dandu-se amplasarea celor N varfuri ale lantului muntos, stabiliti o modalitate de dispunere a celor K statii de telecabine astfel incat lungimea totala a cablurilor folosite pentru conectare sa fie minima, cu restrictiile de mai sus.
Se garanteaza ca, pe toate testele date la evaluare, conectarea va fi posibila.

Date de intrare

Prima linie contine trei numere intregi N, K si L, separate prin spatii, cu semnificatiile de mai sus. Urmatoarele N linii contin coordonatele varfurilor; linia i + 1 contine coordonatele varfului i, Xi si Hi, separate printr-un spatiu.

Date de iesire

  • pe prima linie lungimea totala minima a cablurilor, rotunjita la cel mai apropiat numar intreg (pentru orice intreg Q, Q.5 se rotunjeste la Q+1;
  • pe a doua linie K numere distincte intre 1 si N, ordonate crescator, numerele varfurilor in care se vor infiinta statii de telecabine.

Restrictii

  • 2 ≤ N ≤ 100
  • 2 ≤ K ≤ 30 si K ≤ N
  • 0 ≤ L, Xi, Hi ≤ 100.000 si Xi < Xi+1

Exemplu

munte2.inmunte2.out
7 5 11
0 16
4 3
6 8
7 4
12 16
13 16
14 16
22
1 3 5 6 7

Explicatie

  • Trasarea unui cablu direct intre varfurile 1 si 5 ar fi contravenit restrictiei referitoare la lungimea maxima a unui cablu; in plus, s-ar fi obtinut o solutie cu 2 statii de telecabine in loc de 3 (deci solutia ar fi invalida si pentru valori mari ale lui L);
  • pentru a ilustra restrictia introdusa de formele de relief, precizam ca varfurile 1 si 4 nu au putut fi conectate direct datorita inaltimii varfului 3. De asemenea, varfurile 5 si 7 nu au putut fi conectate direct datorita inaltimii varfului 6.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?