Des combats très simplifiés

...mais une stratégie difficile à trouver.

Afin de vous entraîner à la stratégie, votre centre propose des combats factices de Pokémons. Dans ces combats factices, lorsque deux Pokémons s'affrontent (pour de faux), celui qui a le plus de points de vie (PV) gagne systématiquement. Son dresseur marque alors un nombre de points égal à la somme des points de vie des deux Pokémons. Si les deux Pokémons ont le même nombre de points de vie, le match est nul et personne ne marque.

Les combats sont organisés de la façon suivante. Le premier dresseur choisit l'ordre dans lesquel il fera combattre ses Pokémons, et le second pour s'initier à la stratégie, doit choisir dans quel ordre il fera combattre les siens, en connaissant les choix de son adversaire. Vous êtes le second dresseur.

Supposons que le premier dresseur ait 4 Pokémons, ayant pour nombre de PV : (30, 100, 110, 60). Sachant qu'il veut les faire combattre dans cet ordre, vous devez choisir dans quel ordre présenter vos propres Pokémons : (20, 120, 80, 50)

Si vous choisissez :

  • 20, 120, 80, 50, vous gagnerez le combat 2, marquerez 220 points et votre adversaire 350.
  • 50, 120, 80, 20, vous gagnerez les combats 1 et 2, marquez 300 et votre adversaire 270.
  • 50, 20, 120, 80, vous gagnerez les combats 1, 3 et 4, marquerez 450 points et votre adversaire 120.

Cette dernière combinaison est la meilleure que vous puissiez trouver, et c'est la seule qui vous permet d'atteindre ce score.

L'objectif du défi est de trouver une stratégie qui maximise votre score. Si plusieurs stratégies vous permettent d'atteindre ce score maximal, vous devez en choisir une qui minimise le score de votre adversaire (pensez qu'en cas de match nul personne ne marque). Si les données d'entrée étaient celle de l'exemple, vous devriez répondre pour valider : 50, 20, 120, 80.

En réalité, il y a un peu plus de quatre Pokémons à faire combattre. L'ordre choisi par votre adversaire et la liste des PV correspondant à vos Pokémons sont donnés en entrée du problème.

Ce problème est tiré de c0d1ng UP 2017

Type de retour

Une séquence de nombres

Entrée du problème

  • vous : (130, 150, 120, 70, 50, 160, 160, 130, 70, 60, 70, 30, 30, 160, 190, 140, 90)
  • adversaire : (140, 150, 60, 30, 60, 170, 40, 150, 170, 30, 190, 170, 200, 70, 140, 130, 40)

Formulaire de réponse

Vous devez être connecté pour pouvoir répondre aux défis

Tags : cup17 combinatoire