DIFFICULTE
LIMITE DE MEMOIRE
16000 ko
LIMITE DE TEMPS
1000 ms
É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
EXEMPLE(S) D'ENTREE/SORTIE
Exemple 1
en entrée ...
10 0 3 -1 7 8 5 9 2 -1 0 |
5 |
