Les prisonniers – Qualification 2008

Level 3

É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

Runtime constraints

Maximum memory usage
1000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
10 1
Sample output
1
Sample input
100 36
Sample output
1

Submit your solution

You have to register or log in to be able to submit your solution.