Problem
Devi stampare N parole sulla stampante a caratteri mobili. Stampanti di tipo mobile — sono vecchie stampanti che richiedono piccoli pezzi di metallo (ogni pezzo contiene una lettera) da posizionare in un certo ordine per formare parole. Quindi vengono tutti premuti su un foglio di carta. Questo stampa una parola. La tua stampante ti consente di fare quanto segue:
- Aggiungi una lettera alla fine della parola attualmente sulla stampante.
- Rimuovi l'ultima lettera dalla parola attualmente sulla stampante. Questa operazione può essere eseguita solo se la parola contiene almeno una lettera.
- Stampa la parola attualmente sulla stampante.
Inizialmente, la stampante contiene una parola vuota. Puoi lasciare una parola non vuota alla fine della stampa sulla stampante. Puoi digitare le parole che ti vengono date in qualsiasi ordine.
Ognuna delle tre operazioni richiede un'unità di tempo. Devi trovare una sequenza di operazioni che stampi le N parole date nel minor tempo possibile. Se ci sono diverse sequenze minime, stampane una qualsiasi.
Input
Il tuo programma dovrebbe accettare il seguente input:
Nella prima riga c'è il numero N (1<=N<=25000).
Nelle successive N righe, parole costituite da lettere minuscole dell'alfabeto latino. La lunghezza di ogni parola non supera 20. Tutte le parole sono diverse.
Uscita
Il tuo programma dovrebbe produrre quanto segue:
Nella prima riga M — numero di operazioni.
Nelle righe M successive, una — descrizione delle operazioni. Ogni operazione è descritta da un singolo carattere:
L'aggiunta di un carattere è indicata dal carattere stesso.
L'eliminazione di un carattere è indicata dal carattere "-" (meno, codice ASCII 45).
L'operazione "stampa parola corrente". contrassegnato dal simbolo «P» (lettera latina maiuscola P).
| Input |
Uscita |
|
3
stampa
il
poesia
|
20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
io
n
t
P
|