Revizia anterioară Revizia următoare
| Fișierul intrare/ieșire | benzinarii.in, benzinarii.out | Sursă | puzzle |
|---|---|---|---|
| Autor | Adăugată de |
Cătălin Frâncu
•
Catalin.Francu
|
|
| Timp de execuție pe test | 0.05 sec | Limită de memorie | 8192 KB |
| Scorul tău | N/A | Dificultate |
   1.5
|
Vezi soluțiile trimise | Statistici
Benzinării (clasele 9-10)
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 di față de punctul de start și cantitatea de benzină ci 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ă.
Date de intrare
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 di ci, în ordinea crescătoare a distanțelor di.
Date de ieșire
Î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.
Restricții
- 1 ≤ N ≤ 100.000
- 1 ≤ L ≤ 10.000.000
- 1 ≤ K ≤ 100
- 0 ≤ di < L pentru 1 ≤ i ≤ N
- 0 ≤ ci ≤ K × L pentru 1 ≤ i ≤ N
- c1 + c2 + ... + cN = 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.
Exemplu
| benzinarii.in | benzinarii.out | Explicație |
|---|---|---|
| 21 10 4 2 55 7 27 15 63 17 65 |
3 |
 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. |
