Sabotage – Qualification 2014

Énoncé¶

La vitesse avec laquelle l'entreprise Super Marchand Brothers s'est étendue fait bien des jaloux, aussi les tuyaux sont régulièrement sabotés. Une équipe de plombiers effectue des rondes pour localiser les tuyaux défectueux. Muni d'une suite d'instructions de déplacement, vous devez retrouver le numéro du tuyau à changer.

Voici les trois types d'instructions :

• 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 ainsi qu'une suite d'instructions. Écrivez une fonction qui retourne le numéro du tuyau d'arrivée (entre 1 et N) si l'on part du tuyau numéro 1 et que l'on suit les instructions.

Entrée¶

L'entrée comprendra :

• un nombre N, le nombre de tuyaux sur la planète ;
• sur la ligne suivante, N nombres L₁ à L_N représentant le nombre de cases que vous fait gagner chaque tuyau de 1 à N ;
• sur la ligne suivante, un nombre M, le nombre d'instructions à suivre ;
• sur la ligne suivante, M lettres, une pour chaque instruction.

Sortie¶

Vous afficherez en sortie :

• Le numéro du tuyau d'arrivée (de 1 à N).

Contraintes¶

• 1 <= N <= 100 000
• 0 <= l_i < N
• 1 <= M <= 100 000