Diferențe pentru problema/hibrid între reviziile #34 si #40

== include(page="template/taskheader" task_id="hibrid") ==

_Nota: Limitele difera fata de cele din concurs precum si punctarea testelor (masura temporara), datorita modului in care este configurat nerdarena_
_Revenim cu o actualizare in acest sens_
 

O mașină hibrid se deplasează pe o șosea rectilinie folosind, alternativ, fie motorul termic (pe benzină), fie motorul electric. Axa numerelor întregi poate fi folosită pentru a descrie coordonatele de pe șosea. Deplasarea mașinii folosind motorul electric se efectuează fără taxă, dar unele porțiuni din șosea necesită folosirea motorului termic, ceea ce impune plata anumitor taxe. Se cunoaște lista celor *$P$* porțiuni taxabile de șosea, numerotate de la $1$ la [*$P$*], **oricare două dintre ele fiind disjuncte**. Fiecare porțiune este descrisă de trei numere întregi: [*$st[~i~]$*], [*$dr[~i~]$*] și [*$c[~i~]$*] ($1 ≤ *i* ≤ [*P*]$), cu semnificația că pe porțiunea de șosea situată între coordonatele [*$st[~i~]$*] și [*$dr[~i~]$*] (inclusiv la capetele [*$st[~i~]$*] și [*$dr[~i~]$*]) se va folosi motorul termic și se va achita taxa în valoare de [*$c[~i~]$*] lei. Această taxă se va plăti la fiecare traversare a porțiunii, indiferent de sensul deplasării.
Traseul pe care mașina hibrid îl are de străbătut conține *$N$* borne amplasate pe șosea, numerotate de la $1$ la [*$N$*], în ordinea în care acestea trebuie vizitate. Pentru fiecare dintre cele *$N$* borne se cunoaște coordonata poziției sale pe șosea: $[*x[~1~]*], [*x[~2~]*], [*x[~3~]*], ..., [*x[~N~]*]$. Deplasarea între două borne consecutive de pe traseu, adică între borna *$i$* și borna $[[*i*]+1]$ (pentru fiecare $[*i*]$: $1 ≤ *i* < [*N*]$), se face pe drumul cel mai scurt, respectiv pe segmentul de dreaptă ce unește punctele cu coordonatele $[*x[~i~]*]$ și $[*x[~i+1~]*]$ de pe șosea. **Mașina hibrid va începe traseul din dreptul bornei cu numărul de ordine $1$, adică de la coordonata $x[~1~]$ de pe șosea.** _De asemenea, se știe că nicio bornă de pe traseu nu se află în interiorul sau la capetele porțiunilor taxabile, unde se folosește deplasarea cu motorul termic._

* Întrucât au dimensiuni neglijabile, pot exista și două sau mai multe borne situate la aceeași coordonată pe șosea;
* Pe durata întregului traseu, motorul termic (pe benzină) este utilizat doar pentru parcurgerea porțiunilor taxabile peste care mașina hibrid trebuie să treacă. În rest, se folosește doar motorul electric, pentru a reduce poluarea;

table{width: auto;}.
|_. # |_. Punctaj |_. Restricții |
| 1
| 11
| Pentru efectuarea traseului nu se va trece peste nicio porțiune taxabilă
|
| 2
| 8
| 0 ≤ [*st[~i~]*], *x[~j~]* și [*dr[~i~]*], *x[~j~]* ≤ 70, pentru fiecare *i* și *j*: 1 ≤ *i* ≤ *P* , 1 ≤ *j* ≤ N
|
| 3
| 12
| &#124;[*x[~i+1~]*] − [*x[~i~]*]&#124; &le; 70, pentru fiecare *i*: 1 &le; *i* < *N* și &#124;[*x[~i~]*]&#124; &le; 300 000, pentru fiecare *i*: 1 &le; *i* &le; *N*
|
| 4
| 40
| [*P*], [*N*] &le; 3 000
|
| 5
| 29
| Nu există alte restricții suplimentare
|
 
 

h2. Exemple

table(example).

|_. hibrid.in |_. hibrid.out |_. Explicație |
| 1 2 4
4 8 10

* porțiunea $1$ cuprinde coordonatele: $4$, $5$, $6$, $7$, $8$ și are taxa de $10$ lei la fiecare trecere;
* porțiunea $2$ cuprinde coordonatele: $-10$, $-9$ și are taxa de $22$ de lei la fiecare trecere.
 

 

Traseul pe care mașina hibrid îl are de parcurs este alcătuit din $N = 4$ borne, situate la coordonatele:
$-14$ (prima bornă, **din dreptul căreia se începe traseul**), $20$ (a doua bornă), $-14$ (a treia bornă;
de remarcat că este situată la aceeași coordonată ca și prima bornă!), respectiv $0$ (a patra bornă).