Problem
Sie müssen N Wörter in Movable Type Printer drucken. Movable Type Printers sind alte Drucker, bei denen kleine Metallstücke (jedes Stück enthält einen Buchstaben) in einer bestimmten Reihenfolge angeordnet werden müssen, um Wörter zu bilden. Dann werden sie alle in ein Blatt Papier gepresst. Auf diese Weise wird ein Wort gedruckt. Mit Ihrem Drucker können Sie die folgenden Vorgänge durchführen:
- Fügt einen Buchstaben am Ende des Wortes hinzu, das sich derzeit auf dem Drucker befindet.
- Löscht den letzten Buchstaben aus dem Wort, das sich derzeit auf dem Drucker befindet. Diese Operation kann nur durchgeführt werden, wenn das Wort mindestens einen Buchstaben enthält.
- Druckt das Wort, das sich auf dem Drucker befindet.
Der Drucker enthält zunächst ein leeres Wort. Sie können am Ende des Druckvorgangs ein leeres Wort auf dem Drucker hinterlassen. Die Wörter, die Ihnen gegeben werden, können in zufälliger Reihenfolge gedruckt werden.
Jede der drei Operationen benötigt eine Zeiteinheit. Sie müssen eine Abfolge von Operationen finden, die die Daten von N Wörtern in kürzester Zeit ausdrucken. Wenn es mehrere minimale Sequenzen gibt, geben Sie eine aus.
Eingabe
Ihr Programm sollte die folgenden Eingaben lesen:
In der ersten Zeile ist die Zahl N (1<=N<=25000).
Die folgenden N Zeilen enthalten Wörter, die aus kleinen Buchstaben des lateinischen Alphabets bestehen. Die Länge jedes Wortes überschreitet 20 nicht. Alle Wörter sind unterschiedlich.
Ausgabe
Ihr Programm sollte folgende Daten ausgeben:
In der ersten Zeile M — die Anzahl der Operationen.
In den folgenden M Zeilen wird jeweils ein Zeichen lang beschrieben. Jede Operation wird durch ein einzelnes Zeichen beschrieben:
Das Hinzufügen eines Zeichens wird durch das eigentliche Zeichen gekennzeichnet.
Das Löschen eines Zeichens wird durch das Zeichen «-» (minus, ASCII-Code 45) gekennzeichnet.
Die Operation «das aktuelle Wort»wird durch das Symbol «P» (lateinischer Großbuchstabe P) gekennzeichnet.
| Eingabe |
Ausgabe |
|
3
print
the
poem
|
20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P
|