Hyperchronos partie 1 – Épreuve régionale 2021

Niveau 3

É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$

Contraintes d'exécution

Utilisation mémoire maximum
1000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
2
4 4
Exemple de sortie
1 H
1 H
1 H
0 H
1 A
1 A
1 A
0 H
1 H
1 H
1 H
0 H
1 A
1 A
1 A
0 H