Problem : 248 - Type Printer

Special Judge

Problem Statistics

Solved Member: 22　　Submission: 93　　User Tried: 23

Statement:

你需要利用一台可移動的打印機打印出N 個單詞。這種可移動式打印機是一種老式打印機，它需要你將一些小的金屬塊（每個包含一個字母）放到打印機上以組成單詞。然後將這些小金屬塊壓在一張紙上以打印出這個詞。這種打印機允許你進行下列操作：

• 在打印機當前詞的末端（尾部）添加一個字母；
• 在打印機當前詞的尾部刪去一個字母（將打印機當前詞的最後一個字母刪去）。僅當打印機當前至少有一個字母時才允許進行該操作；
• 將打印機上的當前詞打印出來。

初始時打印機為空，或者說它不含任何帶字母的金屬塊。打印結束時，允許有部分字母留在打印機內。同時也允許你按照任意的次序打印單詞。由於每一個操作都需要一定時間，所以需要你盡可能減少所需操作的總數目（將操作的總數最小化）。

Task:

給定所要打印的N 個單詞，找出以任意次序打印所有單詞所需操作的最小數目，並且輸出一個這樣的操作序列。

限制1 <= N <= 25,000，N為你需要打印的單詞數目。

Input:Output:

你的程序必須從標準輸入中讀取下列數據：

• 第1行包含一個整數N, 表示你需要打印的單詞數。
• 隨後的N行中，每一行都包含一個單詞。每個詞僅由小寫字母('a' – 'z')組成，而且單詞的長度為1到20個字母（包含1和20在內）。所有單詞都不相同。

你必須向標準輸出寫下列數據：

• 第1行包含一個整數M ，表示打印這N 個單詞所需操作的最小數目。
• 隨後的M行中，每一行必須包含一個字符。這些字符描述所做操作的序列。每個操作必須按如下描述：
　　o 添加一個字母用該字母的小寫形式表示
　　o 刪去一個字母用字符'-'(減號, ASCII 碼45)表示
　　o 打印當前詞用字符'P'（大寫字母P）表示

Sample Input:Sample Output:

3
print
the
poem

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

Source:

IOI 2008

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1-1	1000ms	65536kb	10
1-2	1000ms	65536kb
2-1	1000ms	65536kb	10
2-2	1000ms	65536kb
3-1	1000ms	65536kb	10
3-2	1000ms	65536kb
4-1	1000ms	65536kb	10
4-2	1000ms	65536kb
5-1	1000ms	65536kb	10
5-2	1000ms	65536kb
6-1	1000ms	65536kb	10
6-2	1000ms	65536kb
7-1	1000ms	65536kb	10
7-2	1000ms	65536kb
8-1	1000ms	65536kb	10
8-2	1000ms	65536kb
9-1	1000ms	65536kb	10
9-2	1000ms	65536kb
9-3	1000ms	65536kb
10-1	1000ms	65536kb	10
10-2	1000ms	65536kb
10-3	1000ms	65536kb
10-4	1000ms	65536kb