Repli – Qualification 2014

É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 L₁ à L_N 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 <= L_i < N