可動式活字印刷機
昔ながらの可動式活字印刷機を使うには、金属製の小さな文字パーツを並べて単語を作る必要があります。この印刷機では、以下の3つの操作が可能です。
現在の単語の末尾に文字を追加する
もし文字が残っていれば、最後の文字を削除する
現在の単語を印刷する
あなたのタスクは、入力として与えられる n
個の単語を(順序は自由に)すべて印刷するために必要な操作の最小回数を求めるプログラムを書くことです。さらに、その最小回数で単語をすべて印刷できる一連の操作手順も出力してください。
入力
入力の最初の行には、印刷したい単語の数を表す整数 n
(1 ≤ n ≤ 25,000) が与えられます。
その後に続く n
行のそれぞれには、小文字のアルファベット ( 'a' ~ 'z' ) からなる長さ 1 ~ 20 文字の単語が書かれており、すべて相異なる単語です。
出力
最初に、単語をすべて印刷するのに必要な操作の最小回数を表す整数 m
を出力します。
続いて、m
行の各行にわたって、実際の操作を示す1文字を出力してください。操作の表現は次の通りです:
文字を追加するときは、その小文字自体を出力する
最後の文字を削除するときは、マイナス記号
-
(ASCII コード 45) を出力する現在の単語を印刷するときは、大文字の
P
を出力する
例
入力 | 出力 |
---|---|
3 | 20 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB