結果

問題 No.653 E869120 and Lucky Numbers
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:53:35
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 109 ms / 2,000 ms
コード長 1,499 bytes
コンパイル時間 168 ms
コンパイル使用メモリ 82,180 KB
実行使用メモリ 76,812 KB
最終ジャッジ日時 2025-06-12 19:54:32
合計ジャッジ時間 2,701 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

p = input().strip()
p_reversed = p[::-1]

dp = set()
dp.add((0, True, True))

for i in range(len(p_reversed)):
    current_digit = int(p_reversed[i])
    next_dp = set()
    for state in dp:
        c_in, a_h, b_h = state
        a_options = []
        if a_h:
            a_options = [6, 7]
        else:
            a_options = [0]
        b_options = []
        if b_h:
            b_options = [6, 7]
        else:
            b_options = [0]
        for a_i in a_options:
            for b_i in b_options:
                sum_ = a_i + b_i + c_in
                digit_sum = sum_ % 10
                carry_out = sum_ // 10
                if digit_sum != current_digit:
                    continue
                a_h_next_options = []
                if a_h:
                    a_h_next_options = [True, False]
                else:
                    a_h_next_options = [False]
                b_h_next_options = []
                if b_h:
                    b_h_next_options = [True, False]
                else:
                    b_h_next_options = [False]
                for a_h_next in a_h_next_options:
                    for b_h_next in b_h_next_options:
                        next_state = (carry_out, a_h_next, b_h_next)
                        next_dp.add(next_state)
    dp = next_dp
    if not dp:
        break

# Check if any state has carry_out == 0
found = False
for state in dp:
    if state[0] == 0:
        found = True
        break

print("Yes" if found else "No")
0