Téléportations – Regional event 2004

Level 4

Énoncé

On vous décrit un parcours, sous la forme d'un tableau d'entiers, à une dimension. Vous partez de la première case du parcours (index 0 du tableau), et devez atteindre la dernière, en un minimum d'étapes possibles.

A chaque étape, vous vous trouvez à une position du parcours, et vous avez trois possibilités de déplacement :

  • Aller sur la case de droite (index suivant dans le tableau).
  • Aller sur la case de gauche, (index précédent dans le tableau).
  • Vous téléporter à la case dont l'index est indiqué dans la case sur laquelle vous vous trouvez actuellement.

A aucun moment, vous ne pouvez sortir du tableau, et vous n'avez pas le droit d'aller sur une case contenant la valeur -1.

S'il n'est pas possible d'atteindre la dernière case, vous devez afficher la valeur -1.

Entrée

Vous devez lire deux lignes sur l'entrée.

  • La première ligne contient un entier, N, le nombre de cases du parcours.
  • La deuxième ligne contient N entiers, séparés par des espaces : les valeurs contenues dans les cases du parcours, de 0 à N-1.

Sortie

Vous devez écrire un entier sur la sortie : le nombre minimum de déplacements nécessaires pour arriver sur la dernière case du parcours (index N-1), ou -1, s'il n'est pas possible de sortir.

Contraintes

  • 1 <= N <= 1000, où N est le nombre de cases du tableau.
  • -1 <= K < N, où K est la valeur stockée dans une case du tableau.

Commentaire

Voici le détail du parcours de l'exemple :

  • On part de 0
  • On avance vers 1
  • On se téléporte sur 3
  • On se téléporte sur 7
  • On recule vers 6
  • On se téléporte vers 9

Runtime constraints

Maximum memory usage
16000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
10
0 3 -1 7 8 5 9 2 -1 0
Sample output
5

Submit your solution

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