結果

問題 No.653 E869120 and Lucky Numbers
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:51:12
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,113 bytes
コンパイル時間 226 ms
コンパイル使用メモリ 82,248 KB
実行使用メモリ 84,296 KB
最終ジャッジ日時 2025-03-26 15:52:03
合計ジャッジ時間 3,396 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

from collections import defaultdict

# Initialize DP table. Each entry is a dictionary of possible states (carry, a_has_non_zero, b_has_non_zero) to boolean.
dp = [defaultdict(bool) for _ in range(n + 1)]
dp[0][(0, False, False)] = True

for i in range(n):
    current_digit = int(reversed_p[i])
    for state in list(dp[i].keys()):
        carry, a_has, b_has = state
        if not dp[i][state]:
            continue
        # Try all possible digits for a and b (0, 6, 7)
        for d_a in [0, 6, 7]:
            for d_b in [0, 6, 7]:
                total = d_a + d_b + carry
                if total % 10 != current_digit:
                    continue
                new_carry = total // 10
                new_a_has = a_has or (d_a != 0)
                new_b_has = b_has or (d_b != 0)
                # Update the next state
                dp[i + 1][(new_carry, new_a_has, new_b_has)] = True

# Check if the final state is valid: carry 0, both have non-zero digits
if dp[n].get((0, True, True), False):
    print("Yes")
else:
    print("No")
0