Un des domaines effervescent dans la communauté informatique est celui de la théorie des jeux. La théorie des jeux donne un cadre formel à la plupart des jeux "classiques", des échecs au go, en passant par les jeux de cartes et d'autres exoticités. On s'intéresse ici à un jeu très classique. Il s'agit du jeu des allumettes.
Le principe est simple : deux joueurs jouent à tour de rôle. Ils ont à leur disposition un tas d'allumettes en commun. À chaque tour, ils doivent retirer un certain nombre d'allumettes, ce nombre étant défini par les règles (typiquement 1, 2 ou 3). Le joueur qui retire la dernière allumette gagne la partie.
Dans un tel jeu, on appelle position gagnante pour un joueur donné un nombre d'allumettes tel que si c'est son tour de jouer, il peut - en faisant une série de choix judicieux (appelée stratégie gagnante) et pour tous choix de son adversaire - être certain de gagner la partie.
Par exemple, si les règles stipulent qu'un joueur doit retirer 1,2 ou 3 allumettes, et qu'il en reste 2, le joueur qui doit jouer est dans une position gagnante. Il suffit pour lui d'en retirer 2 pour gagner la partie.
La situation où il reste 7 allumettes est également une situation gagnante. En effet, le joueur peut retirer 3 allumettes, l'adversaire devra alors en retirer 1,2 ou 3. Dans tous les cas, le joueur pourra gagner au coup d'après.
Étant donné un nombre d'allumettes, et une liste de coups possibles à jouer (nombre d'allumette(s) qu'il est possible de retirer à chaque coup), faire la somme de tous les coups qui correspondent à une stratégie gagnante du jeu des allumettes (voir contexte). En d'autres termes, il faut déterminer pour chaque coup si celui-ci est le premier d'une série de coups qui assurent le joueur de gagner quels que soient les coups de son adversaire. Le joueur qui gagne la partie est celui qui rend le nombre restant d'allumettes négatif ou nul.
Cette somme devra bien entendu être nulle si aucun coup ne vérifie cette propriété.
L'entrée se sépare en deux lignes. La première contient le nombre d'allumettes dans la partie, la seconde la liste des coups possibles à jouer, séparés par des virgules.
Par exemple, l'entrée suivante correspond à un jeu avec 100 allumettes, où à chaque coup les joueurs peuvent enlever 1, 3 ou 7 allumettes :
100 1 3 7
Le nombre d'allumettes sera toujours inférieur à 30000, le nombre de coups inférieur à 10. Les coups sont tous strictement positifs.
La sortie devra contenir la somme des coups correspondant à une stratégie gagnante suivie d'un retour à la ligne.
entrée :
102 1 2 3
sortie :
2
entrée :
1000 1 3 7
sortie :
0
entrée :
42 1 2 4 7
sortie :
12
Squelettes de codes :
[GROUPFULL:skeleton]