Tarongers P30103


Statement
 

pdf   zip

thehtml

El carrer on viu el professor Oak té diversos tarongers. Algun veí desconegut però amb evidents problemes psicològics ha demanat que se’n treguin les taronges. Com que la petició és totalment absurda, l’ajuntament ha decidit fer-ne cas. Podeu calcular el màxim nombre de taronges que es podran treure?

Suposeu aquest model: Hi ha n tarongers en fila. El taronger i-èsim té ti taronges. Aniran a treure les taronges m treballadors municipals, i tots i cadascun d’ells treurà totes les taronges d’exactament un taronger. Per evitar que els treballadors es distreguin xerrant entre ells, hauran d’estar separats per almenys un taronger.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n i m, seguides de les ti, totes entre 0 i 105. Suposeu 1 ≤ n ≤ 1000, m ≥ 0 i 2m − 1 ≤ n.

Sortida

Per a cada cas, escriviu el màxim nombre de taronges que es podran treure.

Pista

La solució esperada té cost Θ(n · m).

Public test cases

  • Input

    3 0  23 42 10
3 1  23 42 10
3 2  23 42 10
6 3  3 2 1 3 1 0
7 4  1 9 1 100000 1 9 1

    Output

    0
42
33
6
4
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++