Hyperchronos partie 2 – Épreuve régionale 2021

Énoncé¶

tl;dr : Par rapport à la partie 1, $k_i$ peut cette fois-ci être impair et $1\le k_i \le 1000$

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-è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$ peut être à la fois pair ou impair.

Pour tester l'Hyper-horloge, il faut tester toutes les configurations possibles tout en finissant à la position initiale.

Elle fonctionne par séquence d'action, 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 peuvent être parcourues 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 les $N$ lignes suivantes, un entier $k_i$ correspondant au nombre de chiffres sur le cadran de la i-ème horloge. La première ligne correspond à l'horloge $0$, la dernière à 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$
• $1 \le k_i \le 1000$