Les prisonniers – Qualification 2008

Énoncé¶

Dans une mise en scène imaginaire, réalisée pour les seuls besoins de l'exercice, les N gardes du couloir de N cellules d'une prison dans lesquelles sont enfermés N prisonniers se livrent à un jeu étrange avant de partir le soir. Chacun, tour à tour, va changer l'état des portes de certaines cellules : s'il trouve une porte ouverte, il la ferme, et réciproquement s'il trouve une porte fermée, il l'ouvre. Le premier garde change l'état de toutes les portes, le deuxième change l'état d'une porte sur deux (c'est-à-dire des portes 2, 4, 6, 8...), le troisième une porte sur trois (3, 6, 9...). Ce processus se répète jusqu'au dernier garde. Écrivez une fonction qui prend en argument le nombre de gardes (et donc de cellules et de prisonniers) N et un numéro de prisonnier P, et qui renvoie 1 s'il pourra s'échapper le lendemain, 0 sinon.

Contraintes¶

1 <= N <= 1000000000 où N est le nombre de gardes (qui est égal au nombre de prisonniers).

Entrée¶

Deux entiers, séparés par un espace :

• N, le nombre de gardes (qui est égal au nombre de prisonniers)
• P, le numéro du prisonner considéré. 1 <= P <= N

Sortie¶

Un entier :

• 0 si le prisonnier reste enfermé
• 1 si le prisonnier peut sortir