Problem
Vous devez imprimer N mots sur l'imprimante Movable Type. Imprimantes de type mobile — ce sont de vieilles imprimantes qui nécessitent de placer dans un certain ordre de petits morceaux de métal (chaque morceau contenant une lettre) pour former des mots. Ensuite, ils sont tous pressés sur une feuille de papier. Cela imprime un mot. Votre imprimante vous permet d'effectuer les actions suivantes :
- Ajouter une lettre à la fin du mot actuellement sur l'imprimante.
- Supprimez la dernière lettre du mot actuellement sur l'imprimante. Cette opération ne peut être effectuée que si le mot contient au moins une lettre.
- Imprimez le mot actuellement sur l'imprimante.
Initialement, l'imprimante contient un mot vide. Vous pouvez laisser un mot non vide en fin d'impression sur l'imprimante. Vous pouvez taper les mots qui vous sont donnés dans n'importe quel ordre.
Chacune des trois opérations prend une unité de temps. Vous devez trouver une séquence d'opérations qui imprime les N mots donnés en un minimum de temps. S'il y a plusieurs séquences minimales, imprimez-en une seule.
Entrée
Votre programme doit accepter les entrées suivantes :
Sur la première ligne se trouve le nombre N (1<=N<=25000).
Sur les N lignes suivantes, des mots composés de lettres minuscules de l'alphabet latin. La longueur de chaque mot ne dépasse pas 20. Tous les mots sont différents.
Sortie
Votre programme doit afficher ce qui suit :
Sur la première ligne M — nombre d'opérations.
Sur les lignes M suivantes, une — descriptif des opérations. Chaque opération est décrite par un seul caractère :
L'ajout d'un caractère est indiqué par le caractère lui-même.
La suppression d'un caractère est indiquée par le caractère "-" (moins, code ASCII 45).
L'opération "imprimer le mot courant" désigné par le symbole «P» (lettre latine P majuscule).
| Entrée |
Sortie |
3
imprimer
le
poème
20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
je
n
t
P