【AtCoder版！蟻本】ABC079 C - Train Ticket【bit全探索】

AtCoder版！蟻本のbit全探索で類題としてあげられているABC079 CをPythonで解いていきます。

リンク

atcoder.jp

AtCoder Beginner Contest 079 C - Train Ticket

問題文

駅の待合室に座っているjoisinoお姉ちゃんは、切符を眺めています。
切符には 4 つの 0 以上 9 以下の整数 A,B,C,D が整理番号としてこの順に書かれています。
A op1 B op2 C op3 D = 7 となるように、op1,op2,op3 に + か - を入れて式を作って下さい。
なお、答えが存在しない入力は与えられず、また答えが複数存在する場合はどれを出力してもよいものとします。

制約

・0≦A,B,C,D≦9
・入力は整数からなる
・答えが存在しない入力は与えられない

解答例

# bit全探索
num = input()

for i in range(2**(len(num)-1)):
    tmp = int(num[0]) # 計算結果
    ans = num[0] # 解答用の変数
    for j in range(len(num)-1):
        if (i >> j) & 1:
            tmp += int(num[j+1])
            ans += "+"
        else:
            tmp -= int(num[j+1])
            ans += "-"
        ans += num[j+1]
    if tmp == 7:
        break

print(ans + "=7")

解説

op1～4に＋かーのどちらかをいれて計算結果が7になる組み合わせを探す問題です。
＋かーの2通りなのでbit全探索を用いて解きました。

tmpは＋やーを代入したときの計算結果です。
ansは解答のために各桁の数字と＋かーの記号を記録していきます。

bitが1ならopは＋として 次の桁の数字を足し、0ならopはーとして 次の桁の数字をひきます。

4桁の数字の計算が終わったら、その値が7か判定します。
7ならば、問題文が求めている形式で解答すればACでした。

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク