[Ioi2008]TYPE PRINTER 打印机

时间限制:10s      空间限制:64MB

题目描述

你需要利用一台可移动的打印机打印出N 个单词。这种可移动式打印机是一种老式打印机,它需要你将一些小的金属块(每个包含一个字母)放到打印机上以组成单词。然后将这些小金属块压在一张纸上以打印出这个词。这种打印机允许你进行下列操作: • 在打印机当前词的末端(尾部)添加一个字母; • 在打印机当前词的尾部删去一个字母(将打印机当前词的最后一个字母删去)。仅当打印机当前至少有一个字母时才允许进行该操作; • 将打印机上的当前词打印出来。 初始时打印机为空,或者说它不含任何带字母的金属块。打印结束时,允许有部分字母留在打印机内。同时也允许你按照任意的次序打印单词。 由于每一个操作都需要一定时间,所以需要你尽可能减少所需操作的总数目(将操作的总数最小化)。 任务 要求你编写一个程序,给定所要打印的N 个单词,找出以任意次序打印所有单词所需操作的最小数目,并且输出一个这样的操作序列。 限制 1 <= N <= 25,000 N为你需要打印的单词数目。


输入格式

你的程序必须从标准输入中读取下列数据: • 第1行包含一个整数N, 表示你需要打印的单词数。 • 随后的N行中,每一行都包含一个单词。每个词仅由小写字母(‘a’ – ‘z’)组成,而且单词的长度为1到20个字母(包含1和20在内)。 所有单词都不相同。


输出格式

你的程序必须向标准输出写下列数据: • 第1行包含一个整数M ,表示打印这N 个单词所需操作的最小数目。 • 随后的M行中,每一行必须包含一个字符。这些字符描述所做操作的序列。每个操作必须按如下描述: o 添加一个字母用该字母的小写形式表示 o 删去一个字母用字符‘-‘(减号, ASCII 码 45)表示 o 打印当前词用字符‘P’(大写字母P)表示


样例输入

3
print
the
poem

样例输出

20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P

提示

有总计为40分的测试数据,其中N不会超过18。


题目来源

没有写明来源