Avets P62616


Statement
 

pdf   zip

thehtml

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 ≤ eik.

Sortida

Per a cada cas, escriviu el mínim nombre de “xutes”.

Public test cases
  • Input

    4 3  1 1 2 2
    2 9  5 4
    5 3  1 1 1 1 1
    

    Output

    2
    0
    1
    
  • Information
    Author
    Eric Valls
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C C++