El Editor Notepalo |
La compañía Macrohard ha sacado una nueva versión de su editor Notepalo, que puede entender unos pocos comandos de voz. Por ahora sólo reconoce dos comandos de voz: "repetir la última palabra" y "eliminar el último símbolo". El comando "repetir la última palabra" introduce también un espacio en blanco para separar la nueva palabra. La compañía dice que con estos comandos es posible escribir mucho más rápido, porque hay que pulsar menos teclas. Por ejemplo, una frase como "this thin thing" requiere sólo de 6 pulsaciones en el teclado.
Acción | Número de pulsaciones |
Contenido del documento |
Presionar "this" | 4 | This |
Decir repetir la última palabra | 0 | this this |
Decir eliminar el último símbolo | 0 | this thi |
Presionar "n" | 1 | this thin |
Decir repetir la última palabra | 0 | this thin thin |
Presionar "g" | 1 | this thin thing |
Para promocionar su editor, la compañía va a organizar un concurso en el que ganará la persona que consiga escribir un conjunto dado de palabras con el menor número de pulsaciones posible. Es más, el orden de las palabras es arbitrario, excepto la primera que siempre debe escribirse en primer lugar. Así que si las palabras son apple, plum y apricote, habría que escribir primero apple y luego las palabras plum y apricote se pueden intercambiar. Y, lo que es mejor, un buen amigo tuyo te ha dado las palabras que se van a usar en el concurso. Como quieres ganar, debes escribir un programa que encuentre el orden de las palabras que requiera un número mínimo de pulsaciones.
La primera línea de la entrada contiene el número T de casos de prueba, entre 1 y 15. Para cada caso, la primera línea contiene el número de palabras N, entre 1 y 100. A continuación vienen N líneas, cada una con una palabra en minúsculas y no mayor de 100 letras. Recuerda que la primera palabra siempre debe ser escrita en primer lugar.
Para cada caso, la primera línea debe contener el número de pulsaciones que se deben usar para escribir todas las palabras en el editor Notepalo. Después vienen N líneas que contienen el orden de las palabras para conseguir ese mínimo. Si hay varias soluciones valdrá cualquiera de ellas.
Ejemplo de entrada | Ejemplo de salida |
3 3 this thin thing 4 popcorn apple apricote plum 2 hello hello |
6 this thin thing 21 popcorn plum apricote apple 5 hello hello |