Le bon étage – Regional event 2024

Level 1 ⋅ Validation weight: 100%

Énoncé

Avant de rentrer dans le temple des dieux, Jøsëf Marchand doit faire signer son passeport divin. Mais… il ne sait pas dans quel étage du château se trouve le bureau des voyages humains ! Aidez-le à se retrouver dans ce capharnaüm de redirections.

L'entrée est un tableau redirection, où redirection[i] indique l'étage vers lequel vous êtes redirigé depuis l'étage i. Si redirection[i] = i, alors vous n'êtes pas redirigé vers un autre étage, c'est que vous êtes bien arrivé au bureau des voyages humains.

En commençant depuis l'étage 0, aidez Jøsëf Marchand à suivre le fil des redirections et indiquez-lui l'étage du bureau des voyages humains.

Notez que le tableau redirection est donc indexé à 0.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre d'étages.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : redirection, le tableau indiquant vers quels étages Jøsëf Marchand se fait rediriger.

Sortie

En partant de l'étage 0 et en suivant les redirections, affichez sur une ligne l'étage du bureau des voyages humains.

Contraintes

  • $1 \le N \le 50$

Runtime constraints

Maximum memory usage
100000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
6
4 1 1 3 3 5
Sample output
3
Note

Ici, le tableau est composé de six éléments : 4, 1, 1, 3, 3, 5

On commence à l'étage 0 :

  • redirection[0] = 4, on va donc à l'étage 4
  • redirection[4] = 3, on va à l'étage 3
  • redirection[3] = 3, on a donc trouvé le bon étage !

On affiche donc 3.

Sample input
20
5 1 2 3 13 4 6 7 8 9 2 11 11 10 14 15 16 1 2 3
Sample output
2
Note

Ici, le tableau est composé de 20 éléments.

On commence à l'étage 0 :

  • redirection[0] = 5, on va donc à l'étage 5
  • redirection[5] = 4, on va à l'étage 4
  • redirection[4] = 13, on va à l'étage 13
  • redirection[13] = 10, on va à l'étage 10
  • redirection[10] = 2, on va à l'étage 2
  • redirection[2] = 2, on a trouvé le bon étage !

On affiche alors 2.

Sample input
5
0 1 2 3 4
Sample output
0
Note

Ici, le tableau est composé de 5 éléments.

On commence à l'étage 0, et on trouve immédiatement redirection[0] = 0 : on est déjà au bon étage !

On affiche alors 0.

Submit your solution

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