Imprimante à caractères mobiles
Vous disposez d’une imprimante à caractères mobiles, un ancien outil d’impression qui nécessite d’assembler de petites pièces métalliques, chacune portant une lettre, pour composer des mots. Cette imprimante autorise trois opérations :
- ajouter une lettre à la fin du mot en cours
- retirer la dernière lettre si elle existe
- imprimer le mot actuel.
Votre tâche consiste à écrire un programme qui lit en entrée
n mots et détermine le nombre minimal d’opérations nécessaires pour imprimer tous ces mots dans n’importe quel ordre. De plus, le programme doit produire une séquence d’opérations permettant d’atteindre ce minimum.Entrée
La première ligne de l’entrée contient un entier
n (1 ≤ n ≤ 25,000) indiquant le nombre de mots à imprimer.Elle est suivie de
n lignes, chacune contenant un mot constitué de lettres minuscules (de 'a' à 'z'), avec une longueur entre 1 et 20 (inclus). Tous les mots sont distincts.Sortie
Le programme doit afficher un entier
m, correspondant au nombre minimal d’opérations pour imprimer tous les mots.Les
m lignes qui suivent doivent chacune contenir un seul caractère décrivant la séquence d’opérations. Les opérations sont représentées de la manière suivante :- L’ajout d’une lettre est noté par la lettre minuscule elle-même.
- Le retrait de la dernière lettre est noté par le caractère
-(le tiret, code ASCII 45).
- L’impression du mot en cours est notée par le caractère
P(P majuscule).
Exemples
Entrée | Sortie |
3
print
the
poem | 20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB