La granota golafre P40088


Statement
 

pdf   zip

thehtml

En un estany hi ha n pedres 1, …, n en fila. Una granota ha d’anar de la pedra 1 a la n, en principi passant consecutivament per les pedres 2, 3, …El problema és que la granota és molt golafre, i no podrà evitar menjar-se totes les mosques que trobi voltant per cada pedra que visiti. Per evitar engreixar-se massa, la granota pot fer fins a s grans salts endavant, cadascun passant com a molt per sobre de dues pedres (és a dir, des de i pot saltar com a molt fins a i + 3). Quin és el mínim nombre de mosques que la granota es menjarà?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n i s, seguits del nombre de mosques a cada pedra (n naturals entre 0 i 104). Assumiu 2 ≤ n ≤ 1000, i 0 ≤ s < n.

Sortida

Per a cada cas, escriviu el mínim nombre de mosques que la granota es menjarà.

Public test cases
  • Input

    2 0  23 33
    2 1  23 33
    4 0  100 42 3 1000
    4 1  100 42 3 1000
    3 1  10000 10000 10000
    5 1  1000 1000 0 1000 1000
    5 2  1000 1000 0 1000 1000
    5 4  1000 1000 0 1000 1000
    

    Output

    56
    56
    1145
    1100
    20000
    3000
    2000
    2000
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++