Avets P62616
En lloc d’estar entrenant, els representants de la UPC al SWERC es dediquen a fer turisme no convencional per París, mirant com la gent embolica avets a un mercat de nadal. Com que l’algorisme d’embolicar avets és molt costós, una de les persones que s’hi dedica, la Marie, que és asmàtica, cada cert temps ha de “xutar-se” ventolin.
Aquest és el problema a resoldre: La Marie inicialment té energia k. Encara li queden n avets per embolicar, en un ordre fixat, i cada avet i li consumeix energia ei. Cada cop que es “xuta” ventolin, l’energia li torna al nivell original k, i cada cop que embolica un avet, l’energia li disminueix en ei. La Marie no pot tenir mai energia negativa, i només pot “xutar-se” ventolin entre avets. Quin és el mínim nombre de cops que ha de “xutar-se”?
Entrada
L’entrada consisteix en diversos casos, cadascun amb n i k, seguits dels ei. Podeu suposar 1 ≤ n ≤ 105, 1 ≤ k ≤ 106, i 1 ≤ ei ≤ k.
Sortida
Per a cada cas, escriviu el mínim nombre de “xutes”.
Input
4 3 1 1 2 2 2 9 5 4 5 3 1 1 1 1 1
Output
2 0 1
- Author
- Eric Valls
- Language
- Catalan
- Official solutions
- C++
- User solutions
- C C++