Movable Type Printer
У вас есть печатный станок с наборными литерами (movable type printer) — старинное устройство, в котором для формирования слов нужно расставлять небольшие металлические литеры. Этот станок поддерживает три операции:
добавлять букву в конец текущего слова,
убирать последнюю букву (если она есть),
«напечатать» (зафиксировать) текущее слово.
Ваша задача — написать программу, которая получает на вход n слов и делает столько операций, сколько необходимо, чтобы «напечатать» все эти слова в любом порядке, затратив при этом минимальное число операций. После нахождения такой минимальной последовательности нужно вывести её.
Входные данные
В первой строке входных данных задано целое число n (1 ≤ n ≤ 25,000), означающее количество слов, которые нужно «напечатать».
Затем следует n строк, каждая из которых содержит слово из строчных букв (от 'a' до 'z') длиной от 1 до 20 символов включительно. Все слова различны.
Выходные данные
Сначала необходимо вывести число m — минимальное количество операций для «печати» всех слов.
Далее выведите m строк; каждая строка должна содержать один символ, описывающий операцию. При этом:
добавление буквы обозначается самой этой буквой (в нижнем регистре),
удаление последней буквы обозначено символом
-(минус, ASCII-код 45),«печать» текущего слова обозначено символом
P(заглавная латинская буква P).
Примеры
Входные данные | Выходные данные |
|---|---|
3 | 20 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB