Темы --> Информатика --> Структуры данных --> Деревья --> Бор
---> 1 задач <---
Источники --> Личные олимпиады --> Международные олимпиады
    2005(6 задач)
    2006(6 задач)
    2007(6 задач)
    2008(6 задач)
    2009(8 задач)
Страница: 1 Отображать по:
#3302
Type Printer
  
Темы: [Бор]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
128 megabytes

Вам нужно напечатать \(N\) слов на Movable Type Printer. Movable Type Printers — это старые принтеры, для работы которых требуется ставить маленькие металлические кусочки (каждый из кусочков содержит одну букву) в определенном порядке, образуя таким образом слова. Потом все они вдавливаются в лист бумаги. Таким образом печатается одно слово. Ваш принтер позволяет делать следующие операции:

  • Добавить букву в конец слова, находящегося сейчас на принтере.
  • Удалить последнюю букву из слова, находящегося сейчас на принтере. Эту операцию можно делать, только если слово содержит хотя бы одну букву.
  • Напечатать слово, находящееся на принтере (при этом слово никуда не исчезает, можно печатать его ещё раз и ещё раз).

Изначально на принтере содержится пустое слово. В конце печати на принтере можно оставить непустое слово. Слова, которые вам даны, вы можете печатать в произвольном порядке.

Каждая из трёх операций занимает одну единицу времени. Вам нужно найти последовательность операций, которая печатает данные \(N\) слов за минимальное время. Если минимальных последовательностaей несколько, выведите любую.

Входные данные

Ваша программа должна считать следующие входные данные:

  • На первой строке число \(N\) (\(1 \le N \le 25\,000\)).
  • На следующих \(N\) строках слова, состоящие из маленьких букв латинского алфавита. Длина каждого слова не превышает 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
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест