結果

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

ソースコード

diff # 

p = input().strip()
if p == '0':
    print("No")
else:
    n = len(p)
    if n == 1:
        num = int(p)
        if num in {12, 13, 14}:
            print("Yes")
        else:
            print("No")
    else:
        reverse_p = p[::-1]
        m = len(reverse_p)
        dp = [dict() for _ in range(m + 1)]
        dp[0][(0, True, True)] = True

        for i in range(m):
            current_dp = dp[i]
            if not current_dp:
                continue
            for (c, a_h, b_h), _ in current_dp.items():
                a_digits = [6, 7] if a_h else [0]
                b_digits = [6, 7] if b_h else [0]
                for a_d in a_digits:
                    for b_d in b_digits:
                        s = a_d + b_d + c
                        digit_p = s % 10
                        carry_out = s // 10
                        if i < m and digit_p != int(reverse_p[i]):
                            continue
                        if i == m - 1 and carry_out != 0:
                            continue
                        a_h_next_options = [True, False] if a_h else [False]
                        b_h_next_options = [True, False] if b_h else [False]
                        for a_h_next in a_h_next_options:
                            for b_h_next in b_h_next_options:
                                key = (carry_out, a_h_next, b_h_next)
                                dp[i + 1][key] = True

        if (0, False, False) in dp[m]:
            print("Yes")
        else:
            print("No")
0