Наборный принтер
Наборный принтер
Вам необходимо напечатать 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