Back
Close

Recueil d'exercices pour apprendre Python au lycée

M_C
1520.5K views

Inversion en croix

Difficulté : Extrême (100%) Origine : Projet Euler n°331

NxN disques sont placés sur un grille carrée. Chaque disque a une face blanche et une face noire.

A chaque tour, on peut choisir un disque et tourner alors tous les disques de la même ligne et colonne : Il y a donc 2N-1 disques retournés. Le jeu fini quand tous les disques montrent la face blanche. Voici un exemple de jeu sur une grille 5x5.

Jeu

On peut prouver que 3 est le nombre minimum de tours pour finir le jeu.

Le disque en bas à gauche de la grille a pour coordonnées (0,0), celui en bas à droite (N-1,0) et en haut à gauche (0,N-1).

On pose $C_n$ la configuration de la grille avec NxN disques suivante : Un disque de coordonnées (x,y) vérifiant $(N-1)^2\leq x^2 + y^2 \leq N^2$ montre sa face noire. Sinon, il montre sa face blanche. $C_5$ est l'exemple ci-dessus.

On pose $T(N)$ le nombre minimal de tours pour finir le jeu qui commence à la configuration $C_N$ ou 0 si la configuration $C_N$ n'a pas de solution. On a $T(5)=3$. On peut montrer que T(10)=29 et T(1 000)=395253.

Trouver $\sum\limits_{i=3}^{31}T(2^i-i)$

On affichera le résultat avec print.

Remarque : Si vous trouvez une solution qui met moins de 50 sec pour s'exécuter, je suis très intéressé !

Inversion en croix

Create your playground on Tech.io
This playground was created on Tech.io, our hands-on, knowledge-sharing platform for developers.
Go to tech.io