結果

問題 No.1185 完全な3の倍数
ユーザー lam6er
提出日時 2025-03-20 21:12:58
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 46 ms / 2,000 ms
コード長 1,686 bytes
コンパイル時間 223 ms
コンパイル使用メモリ 82,420 KB
実行使用メモリ 57,520 KB
最終ジャッジ日時 2025-03-20 21:14:24
合計ジャッジ時間 3,258 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

def count_perfect_three(N):
    s = str(N)
    n_len = len(s)
    if N < 10:
        return 0
    
    # Count two-digit numbers where sum of digits is divisible by 3 and <= N
    two_digit_count = 0
    for a in range(1, 10):
        for b in range(0, 10):
            num = a * 10 + b
            if num > N:
                continue
            if (a + b) % 3 == 0:
                two_digit_count += 1
    
    # Count numbers with three or more digits where all digits are 0, 3, 6, 9
    # Using digit DP
    allowed_digits = {'0', '3', '6', '9'}
    
    from functools import lru_cache
    
    @lru_cache(maxsize=None)
    def dfs(pos, tight, leading_zero, length):
        if pos == n_len:
            return 1 if length >= 3 else 0
        limit = int(s[pos]) if tight else 9
        total = 0
        for d in range(0, limit + 1):
            new_tight = tight and (d == limit)
            new_leading_zero = leading_zero and (d == 0)
            new_length = length + 1 if not new_leading_zero else length
            
            # Check if the digit is allowed
            if str(d) not in allowed_digits:
                if not new_leading_zero:
                    continue  # invalid digit and already started forming the number
                elif d != 0:
                    continue  # leading_zero but digit is not 0 (since leading_zero can't have other digits)
            
            # Proceed to next position
            total += dfs(pos + 1, new_tight, new_leading_zero, new_length)
        return total
    
    three_or_more_count = dfs(0, True, True, 0)
    
    return two_digit_count + three_or_more_count

N = int(input())
print(count_perfect_three(N))
0