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