Impressora de tipos móveis
Tem uma impressora de tipos móveis, um dispositivo de impressão antigo que requer a disposição de pequenas peças de metal com letras para formar palavras. Esta impressora permite três operações:
- adicionar uma letra ao final da palavra atual
- remover a última letra, se existir
- imprimir a palavra atual
O seu objetivo é escrever um programa que recebe como entrada
n palavras e determina o número mínimo de operações necessário para imprimir todas as palavras em qualquer ordem. Além disso, o programa deve produzir uma sequência de operações que alcance esse mínimo.Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ 25,000), representando o número de palavras a imprimir.Em seguida, surgem
n linhas, cada uma contendo uma palavra formada por letras minúsculas ('a' - 'z') e com comprimento entre 1 e 20 (inclusive). Todas as palavras serão distintas.Saída
O programa deve imprimir um inteiro
m, que representa o número mínimo de operações necessárias para imprimir as palavras.Nas
m linhas seguintes, cada uma deve conter um único carácter que descreva a sequência de operações. As operações devem ser representadas da seguinte forma:- Adicionar uma letra é representado pela própria letra minúscula.
- Remover a última letra é representado pelo carácter
-(hífen, código ASCII 45).
- Imprimir a palavra atual é representado pelo carácter
P(letra maiúscula P).
Exemplos
Entrada | Saída |
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