Le bon étage – Épreuve régionale 2024

Niveau 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$

Contraintes d'exécution

Utilisation mémoire maximum
100000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
6
4 1 1 3 3 5
Exemple de sortie
3
Commentaire

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.

Exemple d'entrée
20
5 1 2 3 13 4 6 7 8 9 2 11 11 10 14 15 16 1 2 3
Exemple de sortie
2
Commentaire

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.

Exemple d'entrée
5
0 1 2 3 4
Exemple de sortie
0
Commentaire

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.