Hâte – Qualification 2014

Énoncé¶

Pour que les plombiers de Super Marchand Brothers soient plus efficaces, vous aimeriez bien déterminer le nombre d'instructions minimal pour accéder à chacun des tuyaux.

Pour rappel, voici la liste des 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 le nombre de cases que vous fait gagner chaque tuyau. Vous devez déterminer le nombre minimal d'instructions pour accéder à chacun des tuyaux.

Entrée¶

L'entrée comprendra :

• un nombre N, le nombre de tuyaux mesurés ;
• sur la ligne suivante, N nombres L₁ à L_N représentant la distance que vous fait gagner chaque tuyau.

Sortie¶

Vous afficherez en sortie :

• N nombres séparés par des espaces, le k-ème correspondant au nombre minimal d'instructions pour accéder au tuyau numéro k.

Contraintes¶

• 1 <= N <= 10 000
• 0 <= L_i < N