Back
Close

Recueil d'exercices pour apprendre Python au lycée

M_C
27K views
Previous: Projet Euler n°121 à 125 Next: Introduction

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 Cn la configuration de la grille avec NxN disques suivante : Un disque de coordonnées (x,y) vérifiant (N1)2x2+y2N2 montre sa face noire. Sinon, il montre sa face blanche. C5 est l'exemple ci-dessus.

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

Trouver i=331T(2ii)

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
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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
codingame x discord
Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
JOIN US ON DISCORD
Online Participants