Drucker mit beweglichen Lettern
Du besitzt einen Drucker mit beweglichen Lettern – ein altes Druckgerät, bei dem kleine Metallplättchen mit Buchstaben angeordnet werden müssen, um Wörter zu setzen. Dieser Drucker ermöglicht drei Operationen:
- Einen Buchstaben am Ende des aktuellen Wortes hinzufügen.
- Den letzten Buchstaben entfernen, falls vorhanden.
- Das aktuelle Wort drucken.
Deine Aufgabe besteht darin, ein Programm zu schreiben, das
n Wörter als Eingabe erhält und die minimale Anzahl von Operationen ermittelt, um alle Wörter in beliebiger Reihenfolge zu drucken. Zusätzlich soll das Programm eine Operationsfolge ausgeben, mit der sich dieses Minimum erreichen lässt.Eingabe
Die erste Zeile der Eingabe enthält eine ganze Zahl
n (1 ≤ n ≤ 25,000), die angibt, wie viele Wörter gedruckt werden sollen.Anschließend folgen
n Zeilen. Jede dieser Zeilen enthält ein Wort aus Kleinbuchstaben (‚a‘–‚z‘) mit einer Länge zwischen 1 und 20 (einschließlich). Alle Wörter sind eindeutig.Ausgabe
Das Programm soll zunächst eine ganze Zahl
m ausgeben, die die minimale Anzahl von Operationen angibt, um alle Wörter zu drucken.In den darauffolgenden
m Zeilen soll jeweils ein Zeichen stehen, das eine Operation beschreibt. Die Operationen werden wie folgt dargestellt:- Das Hinzufügen eines Buchstabens wird durch den entsprechenden Kleinbuchstaben selbst dargestellt.
- Das Entfernen des letzten Buchstabens wird durch das Zeichen '-' (Minus, ASCII-Code 45) dargestellt.
- Das Drucken des aktuellen Wortes wird durch den Großbuchstaben 'P' dargestellt.
Beispiele
Eingabe | Ausgabe |
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