Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

PRINTER - IOI08 Type Printer

You need to print N words on a movable type printer. Movable type printers are those old printers that require you to place small metal pieces (each containing a letter) in order to form words. A piece of paper is then pressed against them to print the word. The printer you have allows you to do any of the following operations:

  • Add a letter to the end of the word currently in the printer.
  • Remove the last letter from the end of the word currently in the printer. You are only allowed to do this if there is at least one letter currently in the printer.
  • Print the word currently in the printer.

Initially, the printer is empty; it contains no metal pieces with letters. At the end of printing, you are allowed to leave some letters in the printer. Also, you are allowed to print the words in any order you like.

As every operation requires time, you want to minimize the total number of operations.

TASK

You must write a program that, given the N words you want to print, finds the minimum number of operations needed to print all the words in any order, and outputs one such sequence of operations.

CONSTRAINTS

1 <= N <= 25,000 The number of words you need to print.

INPUT

Your program must read from the standard input the following data:

  • Line 1 contains the integer N, the number of words you need to print.
  • Each of the next N lines contains a word. Each word consists of lower case letters (‘a’ – ‘z’) only and has length between 1 and 20, inclusive.

All words will be distinct.

OUTPUT

Your program must write to the standard output the following data:

  • Line 1 must contain an integer M that represents the minimum number of operations required to print the N words.
  • Each of the next M lines must contain one character each. These characters describe the sequence of operations done. Each operation must be described as follows:
    • Adding a letter is represented by the letter itself in lowercase
    • Removing the last letter is represented by the character ‘‐‘ (minus, ASCII code 45)
    • Printing the current word is represented by the character ‘P’ (uppercase letter P)

GRADING

For a number of tests, worth a total of 40 points, N will not exceed 18.

EXAMPLE

Sample input
3
print
the
poem

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

Added by:Duc
Date:2008-12-13
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 SCM qobi VB.NET
Resource:IOI 2008 - Egypt

hide comments
2009-07-28 20:46:04 Damir Ferizovic
How can it be that the same solution one time gets 95 points and second time 91 ???
What if there are more solutions ??? Are they being accepted ???
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.