P4683 [IOI 2008] Type Printer

You need to use a movable printer to print $n$ words. This movable printer is an old-style printer: you have to place some small metal blocks (each containing one letter) onto the printer to form a word. Then you press these metal blocks onto a sheet of paper to print the word. The printer allows you to perform the following operations: - Add one letter to the end (tail) of the current word in the printer. - Delete one letter from the end of the current word (remove the last letter). This operation is allowed only when the current word has at least one letter. - Print the current word in the printer. Initially, the printer is empty, i.e., it contains no metal blocks with letters. After finishing all printing, it is allowed to leave some letters in the printer. You are also allowed to print the words in any order. Since each operation takes some time, you need to minimize the total number of operations. You need to write a program that, given the $n$ words to be printed, finds the minimum number of operations needed to print all words in some order, and outputs one such sequence of operations.

- Line $1$ contains an integer $n$, the number of words you need to print. - The next $n$ lines each contain one word. Each word consists only of lowercase letters, and its length is from $1$ to $20$ letters (inclusive). All words are distinct.

The first line contains an integer $m$, the minimum number of operations required to print these $n$ words. The next $m$ lines each contain one character, describing your operation sequence as follows: - To add a letter, output that lowercase letter itself. - To delete a letter, output `-`. - To print the current word, output `P`.

For $40\%$ of the testdata, $n \leq 18$. For $100\%$ of the testdata, $1 \leq n \leq 25000$. Translated by ChatGPT 5