/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 700 点
問題文
N を正の整数とします。 2 つの 2^{N-1} 人チームが対戦する競技があります。
1 から 2^N の番号がついた 2^N 人の人がいます。 すぬけ監督は、彼らを A と B の 2 つの 2^{N-1} 人チームに分けて対戦させる、という操作を何回でも行うことができます。
すぬけ監督は、1 回以上操作を行った後、以下の 2 つの条件の両方を満たすようにしたいです。
- ある整数 n が存在して、1 \leq i < j \leq 2^N を満たす任意の (i,j) について、人 i と人 j が 同じ チームだった回数が n 回
- ある整数 m が存在して、1 \leq i < j \leq 2^N を満たす任意の (i,j) について、人 i と人 j が 異なる チームだった回数が m 回
すぬけ監督の要望を満たすような操作列が存在することが証明できます。そのうち 操作回数が最小 であるようなものの一例を示してください。
制約
- 与えられる入力は全て整数
- 1 \leq N \leq 8
入力
入力は以下の形式で標準入力から与えられる。
N
出力
下記のフォーマットで操作列を出力せよ。
K s_1 s_2 \vdots s_K
ここで、K は操作列の長さを、s_i は i 回目の操作でのチーム分けを表す。
s_{i} は長さ 2^N の A, B のみからなる文字列であり、s_{i} の {j} 文字目が A ならば i 回目の操作で人 j はチーム A に所属していたことを、B ならばチーム B に所属していたことを表す。A, B は s_i において 2^{N-1} 回ずつ出現する必要があることに注意せよ。
K が要望を満たす操作列の長さとして最小であり、操作の結果すぬけ監督の要望が満たされたならば正解となる。
入力例 1
1
出力例 1
1 AB
- 1 回操作を行うことですぬけ監督の要望を満たすことができます。
- 操作は 1 回以上行う必要があることに注意してください。
Score : 700 points
Problem Statement
Let N be a positive integer. Consider a competition where two teams, each with 2^{N-1} players, play against each other.
We have 2^N players numbered 1 through 2^N. Coach Snuke can do the following operation any number of times: separate the players into two teams A and B, each with 2^{N-1} players, and make them play against each other.
He wants to do this operation one or more times so that both of the following conditions are satisfied:
- there exists an integer n such that, for every (i, j) such that 1 \leq i < j \leq 2^N, Player i and Player j have belonged to the same team exactly n times.
- there exists an integer m such that, for every (i, j) such that 1 \leq i < j \leq 2^N, Player i and Player j have belonged to different teams exactly m times.
We can prove that there exist sequences of operations that achieve Snuke's objective. Among those sequences, present one sequence with the minimum possible number of operations.
Constraints
- All values in input are integers.
- 1 \leq N \leq 8
Input
Input is given from Standard Input in the following format:
N
Output
Print a sequence of operations in the format below:
K s_1 s_2 \vdots s_K
Here, K represents the length of the sequence, and s_i represents the division into teams in the i-th operation.
s_i should be a string of length 2^N consisting of A and B. In the i-th operation, if Player j belongs to Team A, the {j}-th character of s_{i} should be A; if Player j belongs to Team B, the {j}-th character of s_{i} should be B. Note that A and B each must occur exactly 2^{N-1} times in each s_i.
Your output will be accepted when K is the minimum possible length of a sequence of operations that achieves the objective, and the sequence actually achieves the objective.
Sample Input 1
1
Sample Output 1
1 AB
- We can satisfy the objective with one operation.
- Note that we must do at least one operation.