Prologin
2025
Énoncé¶
Joseph Marchand est assistant de Chronos et il lui a donné la tâche de tester que l'Hyper-horloge fonctionne.
L'Hyper-horloge est constituée de $N$ horloges. Chacune a une seule aiguille et des nombres sur son cadran. Sur le cadrant de la $i^\text{ème}$ horloge se trouvent $k_i$ nombres, allant de $0$ à $k_i-1$, triés dans le sens horaire. Au départ, toutes les aiguilles des horloges pointent sur $0$.
$k_i$ est forcément pair.
Pour tester l'Hyper-horloge, il faut tester toutes les configurations possibles tout en finissant à la position initiale.
Elle fonctionne par séquence d'actions, c'est-à-dire qu'il est possible de déplacer l'aiguille de n'importe quelle horloge d'un chiffre, dans le sens horaire (H) ou antihoraire (A), un seul déplacement à la fois. Après le dernier déplacement, l'Hyper-horloge doit revenir à sa position initiale. De plus, chaque configuration possible doit être apparue exactement une fois.
Par exemple, sur l'illustration ci-dessous se trouvent deux horloges. La première a 2 chiffres, la seconde en a 4. Les deux aiguilles commencent à 0. Elles forment la configuration $(0; 0)$
Après un décalage dans le sens horaire de l'horloge 1, elles forment la configuration $(0; 1)$
Dans cet exemple, l'ensemble des configurations peut être parcouru avec les actions suivantes : Trois déplacements horaires de l'horloge 1 (de 0 à 3) Un déplacement horaire de l'horloge 0 (de 0 à 1) Trois déplacements anti-horaires de l'horloge 1 (de 3 à 0) Un dernier déplacement horaire de l'horloge 0 (de 1 à 0), qui revient à la position initiale
Ce qui donne la séquence d'action suivante : 1 H 1 H 1 H 0 H 1 A 1 A 1 A 0 H
Joseph n'est pas encore parvenu à faire tourner l'Hyper-Horloge, et commence à perdre espoir. Peux-tu l'aider à trouver la séquence de déplacements à réaliser ? Il existe toujours une solution, qui n'est pas unique.
Entrée¶
L'entrée contiendra :
- Sur la première ligne, un entier $N$ représentant le nombre d'horloges.
- Sur la ligne suivante, $N$ entiers $k_i$ correspondant au nombre de chiffres sur le cadran de la $i^\text{ème}$ horloge séparé par un espace. Le premier entier correspond à l'horloge $0$, le dernier à l'horloge $N-1$
Sortie¶
Afficher une séquence permettant de parcourir toutes les combinaisons.
Sur chaque ligne, indiquer un entier suivi de H ou A. L'entier correspond au numéro de l'horloge, et la lettre à la direction, horaire (H) ou antihoraire (A).
Contraintes¶
- $1 \le N \le 100$
- $2 \le k_i \le 1000$