102162: [AtCoder]ABC216 C - Many Balls

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

Input

题意翻译

### 题意 有一个空盒子。 你可以以任意顺序执行以下两种操作任意次: - 操作 $A$ :往盒子里放入一个球。 - 操作 $B$ :使盒子里球的数量翻倍。 请输出一种**操作次数不超过 $120$ 的方案**使得盒子里有 $N$ 个球。 可以证明一定存在合法方案。 ### 数据范围 - $1 \le N \le 10^{18}$ - 输入的所有数都是整数。 --- ### 输入格式 输入一个整数 $N$ 。 ### 输出格式 输出一个由 `A` 和 `B` 组成的字符串 $S$ , $S$ 的第 $i$ 个字符表示第 $i$ 次操作的种类。 $S$ **至多由 $120$ 个字符**组成。 --- ### 样例解释1 盒子中球数的变化情况为 $0 \xrightarrow{A} 1 \xrightarrow{A} 2 \xrightarrow{B} 4 \xrightarrow{A} 5$ 。 --- ### 样例解释2 盒子中球数的变化情况为 $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$ 。 $\textsf{Translated by @\color{5eb95e}nr0728}.$

Output

分数:300分

问题描述

我们有一个空盒子。

高桥可以按照任意顺序任意次数施放以下两个咒语。

  • 咒语$A$:向盒子里放入一个新球。
  • 咒语$B$:使盒子里的球数翻倍。

告诉我们一种方法,使盒子里恰好有$N$个球,咒语施放次数 最多为120次

在给定的约束条件下,总有一种方法可以实现这一点。

除了咒语外,没有其他方法可以改变盒子里球的数量。

约束条件

  • $1 \leq N \leq 10^{18}$
  • 输入中的所有值都是整数。

输入

从标准输入以以下格式获取输入:

$N$

输出

打印一个由AB组成的字符串$S$。 $S$的第$i$个字符应表示第$i$次施放的咒语。

$S$的长度 最多为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$的长度。

加入题单

上一题 下一题 算法标签: