AtCoder-ABC216 C - Many Balls【Python解答例】
AtCoder Beginner Contest216のC問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 216 - AtCoder
AtCoder Beginner Contest216 C - Many Balls
問題文
空の箱があります。
髙橋君は以下の 2 種類の魔法を好きな順番で好きな回数使えます。
魔法 A ：箱の中にボールを 1 つ増やす
魔法 B ：箱の中のボールの数を 2 倍にする
合計 120 回以内の魔法で、箱の中のボールの数をちょうど N 個にする方法を 1 つ教えてください。
なお、与えられた制約のもとで条件を満たす方法が必ず存在することが示せます。
魔法以外の方法でボールの数を変化させることはできません。
制約
・1≤N≤10 ^18
・入力は全て整数
解答例
n = int(input()) res = "" while n > 0: if n % 2 == 0: n = n // 2 res = "B" + res else: n -= 1 res = "A" + res print(res)
解説
魔法Aでボールを1つ増やし、魔法Bでボールを2倍にするとき、ちょうどN個のボールを作る方法を答える問題です。
魔法の使う順番の文字列はresとしました。
魔法の順番を逆から見ていき、Nが偶数なら魔法Bを使い、奇数なら魔法Aを使うこととしてresに文字を格納していきました。
nが0になるまでwhile文でループさせ、nが偶数ならnを2で割り、文字列resの先頭にBを足します。
nが奇数ならnから1だけ引いて、文字列resの先頭にはAを足していきました。
この操作をnが0になるまで繰り返すことで求める答えとなりました。
ABC216の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
