C - Many Balls

Contest Duration: 2021-08-29(Sun) 12:00 - 2021-08-29(Sun) 13:40 (local time) (100 minutes) Back to Home

C - Many Balls Editorial

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}$ 以下でなければならない。

入力例 1Copy

Copy

出力例 1Copy

Copy

AABA

ボールの数は、 $0 \xrightarrow{A} 1\xrightarrow{A} 2 \xrightarrow{B}4\xrightarrow{A} 5$ と変化します。
AAAAA などの答えも正解になります。

入力例 2Copy

Copy

出力例 2Copy

Copy

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 1Copy

Copy

Sample Output 1Copy

Copy

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 2Copy

Copy

Sample Output 2Copy

Copy

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$ .