結果

問題 No.653 E869120 and Lucky Numbers
ユーザー gew1fw
提出日時 2025-06-12 14:44:30
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,127 bytes
コンパイル時間 397 ms
コンパイル使用メモリ 82,320 KB
実行使用メモリ 83,908 KB
最終ジャッジ日時 2025-06-12 14:45:31
合計ジャッジ時間 3,018 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

from collections import defaultdict

# Each state is a tuple (carry_in, a_started, b_started)
dp = [defaultdict(bool) for _ in range(n + 1)]
dp[0][(0, False, False)] = True

for i in range(n):
    current_p_digit = int(p_reversed[i])
    for state in list(dp[i].keys()):
        carry_in, a_started, b_started = state
        if not dp[i][state]:
            continue
        
        # Try all possible a_digit and b_digit combinations
        for a_digit in [0, 6, 7]:
            new_a_started = a_started or (a_digit != 0)
            for b_digit in [0, 6, 7]:
                new_b_started = b_started or (b_digit != 0)
                
                total = a_digit + b_digit + carry_in
                if total % 10 != current_p_digit:
                    continue
                
                carry_out = total // 10
                new_state = (carry_out, new_a_started, new_b_started)
                
                if i + 1 <= n:
                    dp[i + 1][new_state] = True

if (0, True, True) in dp[n]:
    print("Yes")
else:
    print("No")
0