Diferențe pentru problema/benzinarii între reviziile #1 si #11

benzinarii

Benzinării (clasele 9-10)

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

Poveste și cerință...

Un circuit de Formula 1 este ciclic (duh) și are lungimea de $L$ km. O mașină de curse consumă $K$ litri/km. Pe circuit sunt dispuse $N$ benzinării. Pentru fiecare benzinărie $i$ se cunoaște distanța $d[~i~]$ față de punctul de start și cantitatea de benzină $c[~i~]$ pe care o conține. În plus, cantitatea totală de benzină din toate benzinăriile este exact egală cu $K × L$.
 
Să se găsească o benzinărie astfel încât, pornind din acea benzinărie cu rezervorul gol și alimentând pe parcurs, mașina să poată parcurge o tură completă.

h2. Date de intrare

Fișierul de intrare $benzinarii.in$ ...

Fișierul de intrare $benzinarii.in$ conține pe prima linie numerele întregi [$L$], $K$ și [$N$]. Pe următoarele $N$ linii apar perechi de numere întregi $d[~i~] c[~i~]$, în ordinea crescătoare a distanțelor $d[~i~]$.

h2. Date de ieșire

În fișierul de ieșire $benzinarii.out$ ...

În fișierul de ieșire $benzinarii.out$ se va scrie un număr între 1 și [$N$], reprezentând indicele benzinăriei de start. Dacă există mai multe soluții, se va tipări cea mai mică dintre ele. Dacă problema nu are soluție, se va scrie numărul -1.

h2. Restricții

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100.000$
* $1 ≤ L ≤ 10.000.000$
* $1 ≤ K ≤ 100$
* $0 &le; d[~i~] < L$ pentru $1 &le; i &le; N$
* $0 &le; c[~i~] &le; K × L$ pentru $1 &le; i &le; N$
* $c[~1~] + c[~2~] + ... + c[~N~] = K × L$
* Nu există două benzinării la aceeași coordonată.
* Mașina nu poate merge în sens invers, ci numai în sensul crescător al indicilor benzinăriilor.

h2. Exemplu
table(example).

|_. benzinarii.in |_. benzinarii.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
 
h3. Explicație
 
...

|_. benzinarii.in |_. benzinarii.out |_. Explicație |
| 21 10 4
2 55
7 27
15 63
17 65
| 3
| !problema/benzinarii?benzinarii.png!
 
Mașina pornește de la benzinăria 3 cu rezervorul gol.
Alimentează 63 de litri, consumă 20 și ajunge la benzinăria 4 cu 43 de litri.
Alimentează 65 de litri, consumă 60 și ajunge la benzinăria 1 cu 48 de litri.
Alimentează 55 de litri, consumă 50 și ajunge la benzinăria 2 cu 53 de litri.
Alimentează 27 de litri, consumă 80 și ajunge înapoi la benzinăria 3 cu 0 litri.
Dacă ar porni, de exemplu, de la benzinăria 1, mașina ar rămâne în pană între benzinăriile 2 și 3.
|

== include(page="template/taskfooter" task_id="benzinarii") ==