Hâte – Qualification 2014

Level 4

É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 L1 à LN 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 <= Li < N

Runtime constraints

Maximum memory usage
1000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
6
3 0 2 1 4 2
Sample output
0 1 2 1 2 1
Sample input
10
0 2 0 3 0 0 4 2 1 8
Sample output
0 1 2 2 3 4 3 2 2 1

Submit your solution

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