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