Le concours de Bouf'Gato

Ron a décidé de mettre à profit sa gourmandise afin de faire gagner quelques points à Gryffondor en participant au concours de Bouf'Gato. Le principe est simple, le candidat fait face à une série de 20 gâteaux ensorcelés par Fred et Georges.

À chaque gâteau correspond une valeur nutritive, connue du concurrent (elle est indiquée sur le gâteau avec de la crème).

• Au premier gâteau ingurgité, de valeur nutritive v₁, le concurrent grossit de v₁ grammes.
• Au second gâteau ingurgité, de valeur nutritive v₂, le concurrent grossit de 2 x v₂ grammes.
• Au troisième gâteau ingurgité de valeur nutritive v₃, le concurrent grossit de 3 x v₃ grammes.
• etc.

L'objectif pour tous les concurrents est de grossir le moins possible, car ils participent ensuite à une course de balai. Afin de limiter leur prise de poids, les concurrents ont la possibilité de modifier la position de 5 gâteaux, au maximum, dans la série de 20.

Voici un exemple. Supposons que Ron ait à consommer une série de seulement 10 gâteaux de valeurs nutritives :

11, 15, 30, 10, 16, 5, 45, 55, 12, 40

En prenant les gâteaux dans l'ordre, Ron grossira donc de 11 + 15x2 + 30x3 + 10x4 ... = 1544 grammes.

Mais il peut, par exemple, échanger les deux gâteaux 11 et 55, ce qui donne : 55, 15, 30, 10, 16, 5, 45, 11, 12, 40 et il prendra dans ce cas 55 + 15x2 + 30x3 ... = 1236 grammes

S'il en échange 3, le mieux qu'il puisse faire est de modifier la position des gâteaux de valeurs 55, 40 et 11, pour obtenir : 55, 15, 30, 10, 16, 5, 45, 40, 12, 11. Dans ce cas, il prendra seulement 1178 grammes.

Malheureusement pour Ron, s'il est capable de briller en gobage de gâteaux, trouver les bonnes permutations pour le rendre le plus léger possible, sans faire appel à Hermione, reste difficile.

Pouvez-vous aider Ron et lui indiquer dans quel ordre il devra consommer les gâteaux ? La série de gâteaux est donnée en entrée du problème, et vous pouvez en déplacer 5 au maximum. L'objectif est de minimiser la prise de poids de Ron.

Donnez la réponse sous la forme de la série de gâteaux ; dans l'exemple, ce serait 55, 15, 30, ...