La granota golafre P40088
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à.
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
- Author
- Salvador Roura
- Language
- Catalan
- Other languages
- English
- Official solutions
- C++
- User solutions
- C++