Le jeu de la marelle arithmétique se joue sur la liste des nombres entiers de 0 à N (pour expliquer le problème, nous prendrons N = 100, mais une valeur plus grande sera indiquée par la suite). Un pion est initialement placé sur la case 0. Puis à tour de rôle, chaque joueur doit pousser le pion vers un nombre plus grand. Au maximum, le pion pourra être décalé de k cases par rapport à sa position initiale (k est fixé au début de la partie... prenons 7 par exemple). Un joueur n'a pas le droit de s'arrêter sur une case contenant autre chose qu'un nombre premier, sinon il perd. Pour gagner à ce jeu, il faut que l'adversaire ne puisse plus jouer, ou bien qu'on dépose le pion sur le plus grand nombre premier de la liste (ce sera 97 si N = 100).
Dans ce jeu, et selon la valeur de k (et de N bien entendu), certaines cases sont des cases gagnantes. La case gagnante la plus évidente est le plus grand nombre premier de la liste (97 dans notre exemple) qui assure la victoire par définition. Certaines autres cases sont aussi gagnantes si elles sont suivies d'au moins k nombres composés (un nombre composé plus grand que 1 est un nombre qui n'est pas premier), auquel cas l'autre joueur ne pourra pas jouer et perdra. Il n'y en a qu'une pour N=100 et k=7, c'est la case 89 (suivie de 7 nombres composés). Les cases 97 et 89 sont donc des cases gagnantes.
Certaines cases permettent, si on les atteint, de garantir qu'on pourra toujours atteindre une case gagnante, quoi que joue l'autre joueur. Par exemple, la case 89 peut être atteinte de manière sûre si on joue sur la case 79 (l'autre joueur ne pourra alors jouer que sur la case 83, qui nous permettra d'atteindre la case 89). Elle peut aussi être atteinte de manière sûre si on joue sur la case 61. L'autre joueur ne pourra jouer qu'en 67. Puis nous jouerons en 71, l'autre joueur ne pourra jouer qu'en 73 et nous jouerons en 79... La plus petite case qui permet d'atteindre 89 de manière sûre est la case 5. La case 5 pouvant être jouée au premier coup, la personne qui commence à jouer a donc une stratégie gagnante en jouant la case 5.
L'entrée du défi est constituée de quelques valeurs de k. Pour chacune de ces valeurs de k, vous devez associer le numéro de la case à jouer par le permier joueur, de manière à s'assurer la victoire. Si une telle case n'existe pas pour une valeur de k, vous lui associerez le numéro 0. En outre, notez que la valeur de N à utiliser est maintenant 10000.
Testez votre code
Avec N=10000, si l'entrée vaut 7, 42, 50, vous devrez répondre 5, 0, 7. En effet, avec k = 7, jouer sur la case 5 assure la victoire (nous l'avons vu plus haut). Avec k = 42, aucun nombre premier entre 2 et 41 n'assure la victoire. Et avec k=50, jouer sur la case 7 assure la victoire : ce coup permet forcément au joueur 1 d'atteindre les cases 61, 113, 167, 223, 277, 331.... et de terminer après une longue partie sur la case 9973 (le plus grand nombre premier pour N=10000)