Impresora de tipos móviles
Dispones de una impresora de tipos móviles (movable type printer), un antiguo dispositivo de impresión que necesita acomodar pequeñas piezas metálicas con letras para formar palabras. Esta impresora permite tres operaciones:
- Añadir una letra al final de la palabra actual.
- Eliminar la última letra, si existe.
- Imprimir la palabra actual.
Tu tarea es escribir un programa que reciba como entrada
n palabras y determine el número mínimo de operaciones requeridas para imprimir todas las palabras en cualquier orden. Además, el programa debe mostrar una secuencia de operaciones que alcance ese mínimo.Entrada
La primera línea de la entrada contiene un entero
n (1 ≤ n ≤ 25,000), que representa el número de palabras a imprimir.A continuación, se proporcionan
n líneas, cada una con una palabra compuesta de letras minúsculas ('a' - 'z'), cuya longitud está entre 1 y 20 (inclusive). Todas las palabras serán distintas.Salida
El programa debe imprimir un entero
m, que representa el número mínimo de operaciones necesarias para imprimir las palabras.Luego, en las siguientes
m líneas, se debe imprimir un carácter en cada una para describir la secuencia de operaciones. Las operaciones se representan de la siguiente forma:- Agregar una letra se indica escribiendo esa letra en minúscula.
- Eliminar la última letra se representa con el carácter
-(guion, código ASCII 45).
- Imprimir la palabra actual se representa con la letra
P(mayúscula).
Ejemplos
Input | Output |
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