h2. Cerințe
Să se determine:
1. numărul de ordine al porțiunii taxabile peste care se va trece de cele mai multe ori în călătorie (folosind motorul termic). Dacă există mai multe astfel de porțiuni, se va alege cea cu indicele minim, în funcție de ordinea dată în fișierul de intrare. De asemenea, în caz că nu se va trece peste nicio porțiune taxabilă, acest număr va fi egal cu $-1$.
2. suma totală, exprimată în lei, care trebuie plătită pentru a parcurge traseul stabilit. În caz că nu se va trece peste nicio porțiune taxabilă, atunci această sumă va fi egală cu $0$.
# numărul de ordine al porțiunii taxabile peste care se va trece de cele mai multe ori în călătorie (folosind motorul termic). Dacă există mai multe astfel de porțiuni, se va alege cea cu indicele minim, în funcție de ordinea dată în fișierul de intrare. De asemenea, în caz că nu se va trece peste nicio porțiune taxabilă, acest număr va fi egal cu $-1$.
# suma totală, exprimată în lei, care trebuie plătită pentru a parcurge traseul stabilit. În caz că nu se va trece peste nicio porțiune taxabilă, atunci această sumă va fi egală cu $0$.
h2. Date de intrare
Pe prima linie a fișierului de intrare `hibrid.in` se află, separate între ele prin câte un spațiu, trei numere naturale, $C$, $P$ și $N$, cu semnificațiile din enunț. $C$ poate avea fie valoarea $1$, fie valoarea $2$, în funcție de cerința care trebuie rezolvată. Pe următoarele $P$ linii se află, separate între ele prin câte un spațiu, câte trei numere întregi: $st[i]$, $dr[i]$ și $c[i]$, cu semnificația de mai sus. Pe următoarea linie se află $N$ numere întregi, separate între ele prin câte un spațiu, reprezentând, în ordine, coordonatele bornelor ce trebuie vizitate: $x[ 1 ], x[ 2 ],x[ 3 ], .., x[N]$.
Pe prima linie a fișierului de intrare $hibrid.in$ se află, separate între ele prin câte un spațiu, trei numere naturale, $*C*$, $*P*$ și $*N*$, cu semnificațiile din enunț. $*C*$ poate avea fie valoarea $1$, fie valoarea $2$, în funcție de cerința care trebuie rezolvată. Pe următoarele $*P*$ linii se află, separate între ele prin câte un spațiu, câte trei numere întregi: $*st[~i~]*$, $*dr[~i~]*$ și $*c[~i~]*$, cu semnificația de mai sus. Pe următoarea linie se află $*N*$ numere întregi, separate între ele prin câte un spațiu, reprezentând, în ordine, coordonatele bornelor ce trebuie vizitate: $[*x[~1~]*], [*x[~2~]*], [*x[~3~]*], ..., [*x[~N~]*]$.
h2. Date de ieșire
Fișierul de ieșire `hibrid.out` va conține, pe prima linie, un singur număr întreg, în funcție de cerința care trebuie rezolvată. Dacă $C = 1$, atunci se va rezolva cerința $1$, altfel, se va rezolva cerința $2$.
Fișierul de ieșire $hibrid.out$ va conține, pe prima linie, un singur număr întreg, în funcție de cerința care trebuie rezolvată. Dacă $[*C*] = 1$, atunci se va rezolva cerința $1$, altfel, se va rezolva cerința $2$.
h2. Restricții și precizări
* $2 ≤ P ≤ 100.000$ și $2 ≤ N ≤ 200.000$;
* $-300.000 ≤ st[i] < dr[i] ≤ 300.000$ și $1 ≤ c[i] ≤ 100.000$, pentru fiecare $i$: $1 ≤ i ≤ P$;
* $-1.000.000 ≤ x[i] ≤ 1.000.000$, pentru fiecare $i$: $1 ≤ i ≤ N$;
* $2 ≤ *P* ≤ 100 000$ și $2 ≤ *N* ≤ 200 000$;
* $-300.000 ≤ *st[~i~]* < *dr[~i~]* ≤ 300 000$ și $1 ≤ *c[~i~]* ≤ 100 000$, pentru fiecare $*i*$: $1 ≤ *i* ≤ *P*$;
* $-1.000.000 ≤ *x[~i~]* ≤ 1 000 000$, pentru fiecare $*i*$: $1 ≤ *i* ≤ *N*$;
* Î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;
h2. Exemplul 1
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
| |[*x[~i+1~]*] − [*x[~i~]*]| ≤ 70, pentru fiecare *i*: 1 ≤ *i* < *N* și |[*x[~i~]*]| ≤ 300 000, pentru fiecare *i*: 1 ≤ *i* ≤ *N*
|
| 4
| 40
| [*P*], [*N*] ≤ 3 000
|
| 5
| 29
| Nu există alte restricții suplimentare
|
h2. Exemple
|_. hibrid.in |_. hibrid.out |
table(example).
|_. hibrid.in |_. hibrid.out |_. Explicație |
| 1 2 4
4 8 10
-10 -9 22
-14 20 -14 0
|2
|
h2. Explicație ($C = 1$)
Există două porțiuni taxabile ($P=2$):
| Există două porțiuni taxabile ($P=2$):
* 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ă).
Peste prima porțiune taxabilă se va trece de două ori, iar peste cea de a doua se va trece de trei ori. Prin urmare, se va afișa $2$.
h2. Exemplul 2
|_. hibrid.in |_. hibrid.out |
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ă).
Peste prima porțiune taxabilă se va trece de două ori, iar peste cea de a doua se va trece de trei ori.
Prin urmare, se va afișa $2$.
|
| 2 2 4
4 8 10
-10 -9 22
-14 20 -14 0
| 86
| Conform explicației de mai sus, se va afișa $86$
($2$ treceri * 10 lei/trecere + 3 treceri * 22 lei/trecere $= 86$ de lei, adică suma totală plătită pentru
efectuarea traseului).
|
h2. Explicație ($C = 2$)
Conform explicației de mai sus, se va afișa $86$ ($2$ treceri * 10 lei/trecere + 3 treceri * 22 lei/trecere $= 86$ de lei, adică suma totală plătită pentru efectuarea traseului).
== include(page="template/taskfooter" task_id="hibrid") ==
