Stampante a caratteri mobili
Hai una stampante a caratteri mobili, un antico dispositivo di stampa che richiede l’allineamento di piccoli pezzi di metallo con lettere per comporre le parole. La stampante consente tre operazioni:
- aggiungere una lettera alla fine della parola corrente
- rimuovere l’ultima lettera, se presente
- stampare la parola corrente
Il tuo compito è scrivere un programma che riceve in input
n parole e determina il numero minimo di operazioni necessario per stampare tutte le parole in qualsiasi ordine. Inoltre, il programma deve fornire una sequenza di operazioni che raggiunga questo minimo.Input
La prima riga dell’input contiene un intero
n (1 ≤ n ≤ 25,000) che rappresenta il numero di parole da stampare.Seguono
n righe, ognuna contenente una parola formata da lettere minuscole ('a' - 'z'), con lunghezza compresa tra 1 e 20 caratteri (inclusi). Tutte le parole sono distinte.Output
Il programma deve stampare un intero
m, il numero minimo di operazioni necessario per stampare le parole.Le successive
m righe devono contenere, ciascuna, un singolo carattere a descrivere la sequenza di operazioni. Le operazioni sono rappresentate come segue:- L’aggiunta di una lettera è indicata dalla lettera minuscola stessa.
- La rimozione dell’ultima lettera è indicata dal carattere
-(trattino, codice ASCII 45).
- La stampa della parola corrente è indicata dal carattere
P(lettera maiuscola P).
Esempi
Ingresso | Uscita |
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