/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
空の箱があります。
髙橋君は以下の 2 種類の魔法を好きな順番で好きな回数使えます。
- 魔法 A ：箱の中にボールを 1 つ増やす
- 魔法 B ：箱の中のボールの数を 2 倍にする
合計 \mathbf{120} 回以内の魔法で、箱の中のボールの数をちょうど N 個にする方法を 1 つ教えてください。
なお、与えられた制約のもとで条件を満たす方法が必ず存在することが示せます。
魔法以外の方法でボールの数を変化させることはできません。
制約
- 1 \leq N \leq 10^{18}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
A , B のみからなる文字列 S を出力せよ。
S の i 文字目が A ならば、髙橋君が i 回目に使う魔法が魔法 A であることを表し、B ならば魔法 B であることを表す。
S の長さは \mathbf{120} 以下でなければならない。
入力例 1
5
出力例 1
AABA
ボールの数は、0 \xrightarrow{A} 1\xrightarrow{A} 2 \xrightarrow{B}4\xrightarrow{A} 5 と変化します。
AAAAA などの答えも正解になります。
入力例 2
14
出力例 2
BBABBAAAB
ボールの数は、0 \xrightarrow{B} 0 \xrightarrow{B} 0 \xrightarrow{A}1 \xrightarrow{B} 2 \xrightarrow{B} 4 \xrightarrow{A}5 \xrightarrow{A}6 \xrightarrow{A} 7 \xrightarrow{B}14 と変化します。
S の長さを最小化する必要はありません。
Score : 300 points
Problem Statement
We have an empty box.
Takahashi can cast the following two spells any number of times in any order.
- Spell A: puts one new ball into the box.
- Spell B: doubles the number of balls in the box.
Tell us a way to have exactly N balls in the box with at most \mathbf{120} casts of spells.
It can be proved that there always exists such a way under the Constraints given.
There is no way other than spells to alter the number of balls in the box.
Constraints
- 1 \leq N \leq 10^{18}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
Output
Print a string S consisting of A and B.
The i-th character of S should represent the spell for the i-th cast.
S must have at most \mathbf{120} characters.
Sample Input 1
5
Sample Output 1
AABA
This changes the number of balls as follows: 0 \xrightarrow{A} 1\xrightarrow{A} 2 \xrightarrow{B}4\xrightarrow{A} 5.
There are also other acceptable outputs, such as AAAAA.
Sample Input 2
14
Sample Output 2
BBABBAAAB
This changes the number of balls as follows: 0 \xrightarrow{B} 0 \xrightarrow{B} 0 \xrightarrow{A}1 \xrightarrow{B} 2 \xrightarrow{B} 4 \xrightarrow{A}5 \xrightarrow{A}6 \xrightarrow{A} 7 \xrightarrow{B}14.
It is not required to minimize the length of S.