Des choix cornéliens

Ce défi est tiré de c0d1ngUP 2014

Alice et Bob sont les deux participants d'un challenge de programmation un peu particulier. Il font face en début de journée à une liste de 60 problèmes, chaque problème pouvant rapporter un certain nombre de points. Ils doivent se répartir les problèmes, et chacun essaie d'avoir à résoudre les problèmes qui rapportent le plus de points.

Un protocole a été mis en place pour qu'Alice et Bob se répartissent les problèmes : chacun à leur tour ils pourront choisir le premier ou le dernier de la liste. Pour cela, il ont juste à décider s'ils prennent le problème du début (D) ou le problème de fin (F). Une fois un problème choisi, il est enlevé de la liste des problèmes disponibles. C'est Alice qui commence à choisir son premier problème.

Défi :

La liste des points affectés aux problèmes et donnée en entrée. Sachant qu'Alice et Bob sont tous les deux capables de faire les choix qui vont maximiser leur gain potentiel, et qu'ils préféreront toujours prendre le problème du début dans le cas où les deux alternatives promettent le même gain final, quelle sera la séquence de D et de F qu'ils vont produire ?

Testez votre code :

Si la liste des problèmes était (2,20,10,1,3,1), les problèmes seraient choisis ainsi :

Alice prend le problème de fin (F), il reste (2,20,10,1,3)
Bob prend le problème de fin (F), il reste (2,20,10,1)
Alice prend le problème de fin (F), il reste (2,20,10)
Bob prend le problème de début (D), il reste (20,10). Prendre le problème de fin l'aurait amené au même score. Lorsqu'il a ainsi le choix, il préfère toujours le problème de début
Alice prend le problème de début (D), il reste (10)
Bob prend le dernier problème restant (D ou F), il ne reste plus rien

En faisant ces choix, Alice totalise 22 points et Bob en totalise 15. Sachant que chacun joue au mieux, aucun d'eux ne peut espérer faire plus que ce score là. Une séquence de choix optimaux serait donc : FFFDDD (ou FFFDDF puisque le dernier pris est à la foix au début et à la fin).

Attention, faire le meilleur choix ne veut pas dire prendre le problème qui a le plus de points entre le premier et le dernier. Il faut voir un peu plus loin : c'est le score final qu'on veut maximiser. C'est pour cette raison qu'Alice a commencé par prendre le 1 final et non le 2 initial. En prenant le 2, elle aurait eu un moins bon score (car Bob aurait ainsi eu accès au 20... et au final Alice n'aurait pu avoir que 15 points au lieu de 22)

Voici un autre exemple. Si la liste des problèmes est (1,8,2,3,7,6,4,5) alors la partie jouée sera FDDFDDDD, ce qui donnera un total de 22 pour Alice et 14 pour Bob.