Problem
La sauterelle saute sur des colonnes situées sur la même ligne à égale distance les unes des autres. Les colonnes ont des numéros de série de 1 à N . Au début, la sauterelle est assise sur un poteau portant le numéro 1. Il peut sauter de 1 à K mesures, en comptant à partir de la mesure actuelle.
Sur chaque colonne, la Sauterelle peut gagner ou perdre plusieurs pièces d'or (ce nombre est connu pour chaque colonne). Déterminez comment la sauterelle doit sauter pour collecter le plus de pièces d'or. Gardez à l'esprit que la sauterelle ne peut pas sauter en arrière.
Entrée :
- la première ligne contient deux nombres naturels : N et K (\(2 <= N ,\ K < = 10000\)), séparés par des espaces ;
- dans la deuxième ligne, des entiers N-2 séparés par des espaces – le nombre de pièces que la sauterelle reçoit sur chaque colonne, de la 2ème à la N-1ème. Si ce nombre est négatif, la sauterelle perd des pièces.
Il est garanti que tous les nombres en modulo ne dépassent pas 10000.
Sortie :
- sur la première ligne, le programme doit afficher le nombre maximum de pièces que le Grasshopper peut collecter ;
- la deuxième ligne affiche le nombre de sauts de Grasshopper ;
- sur la troisième ligne – numéros de toutes les colonnes visitées par le Grasshopper (séparés par un espace dans l'ordre croissant).
S'il y a plusieurs bonnes réponses, écrivez-en une.
Exemples
| # |
Entrée |
Sortie |
| 1 |
5 3
2 -3 5
7
3
1 2 4 5