Repli – Qualification 2014

Niveau 5

Énoncé

Un risque du travail classique est qu'un plombier se perde en chemin : il peut en effet arriver que certains plombiers ne sachent plus sur quel tuyau ils se trouvent. Pour les rassurer, vous aimeriez bien leur communiquer une suite d'instructions leur permettant de revenir à l'entreprise quelle que soit leur position. Pour solliciter au minimum leur mémoire, vous souhaitez que cette suite d'instructions salvatrice soit la plus courte possible.

Pour rappel, la liste d'instructions possibles :

  • Avancer (noté « A ») indique qu'il faut avancer d'une case ;
  • Reculer (noté « R ») indique qu'il faut reculer d'une case ;
  • Tuyau (noté « T ») indique qu'il faut emprunter le tuyau de la case courante, qui vous fait avancer d'un certain nombre de cases.

On vous donne une liste de nombres représentant la distance que vous fait gagner chaque tuyau, sachant que le réseau conserve l'ordre, écrivez une fonction qui renvoie le plus petit nombre de mouvements à effectuer pour rentrer au tuyau numéro 1 quel que soit le tuyau de départ.

Entrée

L'entrée comprendra :

  • un nombre N, le nombre de tuyaux ;
  • sur la ligne suivante, N nombres L1 à LN représentant la longueur de chaque tuyau.

Sortie

Vous afficherez en sortie :

  • le nombre minimum de mouvements à effectuer pour rentrer au tuyau numéro 1 quel que soit le tuyau d'où on part, ou -1 s'il est impossible de tous les réunir.

Contraintes

  • 1 <= N <= 250
  • 0 <= Li < N

Contraintes d'exécution

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

Exemples d'entrée/sortie

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

Une plus courte suite d'instructions est TTRTA.

Exemple d'entrée
5
2 2 2 2 2
Exemple de sortie
-1