/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 700 点
問題文
英小文字からなる長さ N の文字列 S が与えられます。S の i 文字目を S_i とします。
N 個の島が円環状に並んでおり、時計回りに島 1、島 2、\ldots、島 N の順で番号が付けられています。特に、島 N の時計回りの隣の島は島 1 です。島 i には文字 S_i が書かれています。はじめ、それぞれの島には人が 1 人ずついます。
あなたは次の操作を 0 回以上行うことができます。
- S に含まれる文字 c を 1 つ選ぶ。すべての人はそれぞれ現在いる島を出発し、時計回りに島を 1 個ずつ移動する。出発後に文字 c が書かれた島に初めて到着した時点で止まる。現在いる島に文字 c が書かれている場合でも出発する。
操作をすべて終えた後に人が 1 人以上いる島の個数としてあり得る最小値を K とします。
K と、操作後に人が 1 人以上いる島の個数を K にする操作列を求めてください。
なお、この問題の制約の下で、操作後に人が 1 人以上いる島の個数を K にする長さ 10^6 以下の操作列が必ず存在することが証明できます。
制約
- 1 \le N \le 1000
- S は英小文字からなる長さ N の文字列
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
操作回数を表す整数を L、操作列を表す文字列を X として、以下の形式で出力せよ。
K L X
L=0 の場合、3 行目は空行として出力せよ。
L は 0 \le L \le 10^6 を満たさなければならない。
X は S に含まれる文字からなる長さ L の文字列でなければならず、X の i 文字目は i 回目の操作で選ぶ文字を表す。
操作列 X に従って操作した後、人が 1 人以上いる島の個数は K でなければならない。
条件を満たす出力が複数存在する場合、どれを出力してもよい。
入力例 1
4 abca
出力例 1
1 1 b
文字 b を選ぶ操作を行うと、すべての人が文字 b が書かれた島に集まります。人がいる島は 1 個になり、これが最小です。
入力例 2
4 aabb
出力例 2
1 2 ab
はじめに a を、次に b を選ぶことで、すべての人が同じ島に集まります。人がいる島は 1 個になり、これが最小です。
入力例 3
4 aaaa
出力例 3
4 0
どの操作を行っても、それぞれの人は時計回りに次の島へ移動します。したがって、人がいる島の個数は常に 4 であり、K=4 です。この出力例では操作を 1 回も行いません。
Score : 700 points
Problem Statement
You are given a string S of length N consisting of lowercase English letters. Let S_i denote the i-th character of S.
There are N islands arranged in a circle, numbered island 1, island 2, \ldots, island N in clockwise order. In particular, the island clockwise-adjacent to island N is island 1. The character S_i is written on island i. Initially, there is one person on each island.
You can perform the following operation zero or more times.
- Choose one character c that appears in S. Every person departs from the island they are currently on and moves one island at a time in the clockwise direction. Each person stops as soon as they first arrive, after departing, at an island on which the character c is written. Even if the island a person is currently on has the character c written on it, that person still departs.
Let K be the minimum possible number of islands that have one or more people on them after all operations are finished.
Find K, and a sequence of operations that makes the number of islands with one or more people equal to K after the operations.
Under the constraints of this problem, it can be proved that there always exists a sequence of operations of length at most 10^6 that makes the number of islands with one or more people equal to K.
Constraints
- 1 \le N \le 1000
- S is a string of length N consisting of lowercase English letters.
- N is an integer.
Input
The input is given from Standard Input in the following format:
N S
Output
Let L be an integer representing the number of operations, and let X be a string representing the sequence of operations. Output in the following format:
K L X
If L=0, output the third line as an empty line.
L must satisfy 0 \le L \le 10^6.
X must be a string of length L consisting of characters that appear in S, and the i-th character of X represents the character chosen in the i-th operation.
After performing the operations according to the sequence X, the number of islands with one or more people must be K.
If multiple outputs satisfy the conditions, you may output any of them.
Sample Input 1
4 abca
Sample Output 1
1 1 b
If we perform the operation choosing the character b, everyone gathers on the island on which the character b is written. The number of islands with people becomes 1, and this is the minimum.
Sample Input 2
4 aabb
Sample Output 2
1 2 ab
By choosing a first and then b, everyone gathers on the same island. The number of islands with people becomes 1, and this is the minimum.
Sample Input 3
4 aaaa
Sample Output 3
4 0
No matter which operation is performed, each person moves to the next island in the clockwise direction. Therefore, the number of islands with people is always 4, so K=4. In this sample output, no operation is performed.