France-IOI
Contexte
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.
Enoncé
É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é.
Limites de temps et de mémoire (Python)
- Temps : 1 s sur une machine à 1 GHz.
- Mémoire : 8 000 ko.
Entrée
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.
Sortie
La sortie devra contenir la somme des coups correspondant à une stratégie gagnante suivie d'un retour à la ligne.
Exemples
Exemple 1
entrée :
102 1 2 3
sortie :
2
Exemple 2
entrée :
1000 1 3 7
sortie :
0
Exemple 3
entrée :
42 1 2 4 7
sortie :
12
Commentaires
Squelettes de codes :
[GROUPFULL:skeleton]Vous devez être connecté(e) pour résoudre ce problème.
L'inscription ne prendra qu'une minute et vous pourrez alors résoudre les exercices puis faire valider automatiquement vos solutions.
Une fois identifié(e), vous pourrez demander sur cette page des conseils pour résoudre le sujet ou demander de l'aide sur le forum d'entraide.
Lorsque vous serez connecté(e), vous pourrez voir vos actions ici.
Une correction détaillée sera disponible lorsque vous aurez résolu le sujet.