ABC解説

【pythonでABC216を解説】C - Many Balls

問題概要

問題ページ

C - Many Balls
C - Many Balls

問題ページへ移動する

問題文

空の箱があります。
髙橋君は以下の \(2\) 種類の魔法を好きな順番で好きな回数使えます。

  • 魔法 \(A\) ：箱の中にボールを \(1\) つ増やす
  • 魔法 \(B\) ：箱の中のボールの数を \(2\) 倍にする

合計 \(\mathbf{120}\) 回以内の魔法で、箱の中のボールの数をちょうど \(N\) 個にする方法を \(1\) つ教えてください。
なお、与えられた制約のもとで条件を満たす方法が必ず存在することが示せます。

魔法以外の方法でボールの数を変化させることはできません。

制約

  • \(1 \leq N \leq 10^{18}\)
  • 入力は全て整数

問題の考察

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    ans = []
    for i in range(200):
        if n == 1:
            ans.append("A")
            break
        if n % 2 == 0:
            ans.append("B")
            n //= 2
        else:
            ans.append("A")
            n -= 1
    print("".join(list(reversed(ans))))


if __name__ == '__main__':
    solve()

-ABC解説
-