Наборный принтер
Наборный принтер
Вам необходимо напечатать N
слов на наборном принтере. Наборный принтер - это такой старый принтер, в который требуется устанавливать маленькие металлические элементы (каждый из которых содержит букву) для того, чтобы формировать слова. После этого к ним прижимается лист бумаги, чтобы отпечатать слово. Ваш принтер позволяет выполнять следующие операции:
- Добавлять букву в конец слова, которое набрано в принтере.
- Удалять последнюю букву из слова, которое набрано в принтере. Это можно делать только в том случае, когда в принтере установлена хотя бы одна буква.
- Печатать слово, набранное в принтере.
Вначале принтер пуст: он не содержит металлических элементов с буквами. По окончании печати разрешается оставлять в принтере некоторые буквы. Также можно печатать слова в любом порядке, который вам нравится. Поскольку каждая операция занимает некоторое время, вы хотите минимизировать общее количество операций.
Вы должны написать программу, которая по заданным N
словам находит минимальное количество операций, необходимых для печати всех этих слов в любом порядке, и выводит одну из таких последовательностей операций.
1 <= N <= 25 000
(N
- Количество слов, которые необходимо напечатать)
Входные данные
Ваша программа должна читать из стандартного ввода следующие данные:
- Строка 1 содержит целое число
N
- количество слов, которые необходимо напечатать. - Каждая из последующих
N
строк содержит слово. Каждое слово состоит только из маленьких латинских букв ('a
' - 'z
') и имеет длину от 1 до 20 символов, включительно.
Все слова различны.
Выходные данные
Ваша программа должна вывести в стандартный вывод следующие данные:
- Строка 1 должна содержать целое число
M
, которое означает минимальное количество операций, требуемых для печатиN
слов. Каждая из последующих
M
строк должна содержать по одному символу. Эти символы описывают последовательность выполняемых операций. Каждая операция должна быть описана следующим образом:Добавление буквы обозначается самой буквой, набранной в нижнем регистре
- Удаление последней буквы обозначается символом '-' (минус,
ASCII
код 45) - Печать текущего слова обозначается символом '
P
' (большая латинская букваP
)
3 print the poem
20 t h e P - - - p o e m P - - - r i n t P