Problem: You are given an integer N. Among the integers between 1 and N (inclusive), how many _Shichi-Go-San numbers_ (literally "Seven-Five-Three numbers") are there?  Here, a Shichi-Go-San number is a positive integer that satisfies the following condition:    * When the number is written in base ten, each of the digits `7`, `5` and `3` appears at least once, and the other digits never appear.

Submission attempts (in order):
N = int(input())
n = str(N)
keta = len(n)



dp = [[[[[0] * 2 for _ in range(2)] for __ in range(2)] for ___ in range(2)] for ____ in range(keta+1)]
dp[0][0][0][0][0] = 1


for d in range(keta):
    now_digit = int(n[d])
    for i in range(10):
        if i == 3:
            if i < now_digit:
                dp[d+1][1][1][0][0] += dp[d][0][1][0][0] + dp[d][0][0][0][0] + dp[d][1][1][0][0] + dp[d][1][0][0][0]
                dp[d+1][1][1][1][0] += dp[d][0][1][1][0] + dp[d][0][0][1][0] + dp[d][1][1][1][0] + dp[d][1][0][1][0]
                dp[d+1][1][1][0][1] += dp[d][0][1][0][1] + dp[d][0][0][0][1] + dp[d][1][1][0][1] + dp[d][1][0][0][1]
                dp[d+1][1][1][1][1] += dp[d][0][1][1][1] + dp[d][0][0][1][1] + dp[d][1][1][1][1] + dp[d][1][0][1][1]
            elif i == now_digit:
                dp[d+1][1][1][0][0] += dp[d][1][1][0][0] + dp[d][1][0][0][0] 
                dp[d+1][1][1][1][0] += dp[d][1][1][1][0] + dp[d][1][0][1][0] 
                dp[d+1][1][1][0][1] += dp[d][1][1][0][1] + dp[d][1][0][0][1] 
                dp[d+1][1][1][1][1] += dp[d][1][1][1][1] + dp[d][1][0][1][1] 
                
                dp[d+1][0][1][0][0] += dp[d][0][1][0][0] + dp[d][0][0][0][0] 
                dp[d+1][0][1][1][0] += dp[d][0][1][1][0] + dp[d][0][0][1][0] 
                dp[d+1][0][1][0][1] += dp[d][0][1][0][1] + dp[d][0][0][0][1] 
                dp[d+1][0][1][1][1] += dp[d][0][1][1][1] + dp[d][0][0][1][1] 
            else:
                dp[d+1][1][1][0][0] += dp[d][1][1][0][0] + dp[d][1][0][0][0] 
                dp[d+1][1][1][1][0] += dp[d][1][1][1][0] + dp[d][1][0][1][0] 
                dp[d+1][1][1][0][1] += dp[d][1][1][0][1] + dp[d][1][0][0][1] 
                dp[d+1][1][1][1][1] += dp[d][1][1][1][1] + dp[d][1][0][1][1] 
        elif i == 5:
            if i < now_digit:
                dp[d+1][1][0][1][0] += dp[d][0][0][1][0] + dp[d][0][0][0][0] + dp[d][1][0][1][0] + dp[d][1][0][0][0]
                dp[d+1][1][0][1][1] += dp[d][0][0][1][1] + dp[d][0][0][0][1] + dp[d][1][0][1][1] + dp[d][1][0][0][1]
                dp[d+1][1][1][1][0] += dp[d][0][1][1][0] + dp[d][0][1][0][0] + dp[d][1][1][1][0] + dp[d][1][1][0][0]
                dp[d+1][1][1][1][1] += dp[d][0][1][1][1] + dp[d][0][1][0][1] + dp[d][1][1][1][1] + dp[d][1][1][0][1]
            elif i == now_digit:
                dp[d+1][1][0][1][0] += dp[d][1][0][1][0] + dp[d][1][0][0][0]
                dp[d+1][1][0][1][1] += dp[d][1][0][1][1] + dp[d][1][0][0][1]
                dp[d+1][1][1][1][0] += dp[d][1][1][1][0] + dp[d][1][1][0][0]
                dp[d+1][1][1][1][1] += dp[d][1][1][1][1] + dp[d][1][1][0][1]

                dp[d+1][0][0][1][0] += dp[d][0][0][1][0] + dp[d][0][0][0][0] 
                dp[d+1][0][0][1][1] += dp[d][0][0][1][1] + dp[d][0][0][0][1] 
                dp[d+1][0][1][1][0] += dp[d][0][1][1][0] + dp[d][0][1][0][0] 
                dp[d+1][0][1][1][1] += dp[d][0][1][1][1] + dp[d][0][1][0][1] 
            else:
                dp[d+1][1][0][1][0] += dp[d][1][0][1][0] + dp[d][1][0][0][0] 
                dp[d+1][1][0][1][1] += dp[d][1][0][1][1] + dp[d][1][0][0][1] 
                dp[d+1][1][1][1][0] += dp[d][1][1][1][0] + dp[d][1][1][0][0] 
                dp[d+1][1][1][1][1] += dp[d][1][1][1][1] + dp[d][1][1][0][1] 
        elif i == 7:
            if i < now_digit:
                dp[d+1][1][0][0][1] += dp[d][0][0][0][1] + dp[d][0][0][0][0] + dp[d][1][0][0][1] + dp[d][1][0][0][0]
                dp[d+1][1][0][1][1] += dp[d][0][0][1][1] + dp[d][0][0][1][0] + dp[d][1][0][1][1] + dp[d][1][0][1][0]
                dp[d+1][1][1][0][1] += dp[d][0][1][0][1] + dp[d][0][1][0][0] + dp[d][1][1][0][1] + dp[d][1][1][0][0]
                dp[d+1][1][1][1][1] += dp[d][0][1][1][1] + dp[d][0][1][1][0] + dp[d][1][1][1][1] + dp[d][1][1][1][0]
            elif i == now_digit:
                dp[d+1][1][0][0][1] += dp[d][1][0][0][1] + dp[d][1][0][0][0] 
                dp[d+1][1][0][1][1] += dp[d][1][0][1][1] + dp[d][1][0][1][0] 
                dp[d+1][1][1][0][1] += dp[d][1][1][0][1] + dp[d][1][1][0][0] 
                dp[d+1][1][1][1][1] += dp[d][1][1][1][1] + dp[d][1][1][1][0] 
                
                dp[d+1][0][0][0][1] += dp[d][0][0][0][1] + dp[d][0][0][0][0] 
                dp[d+1][0][0][1][1] += dp[d][0][0][1][1] + dp[d][0][0][1][0] 
                dp[d+1][0][1][0][1] += dp[d][0][1][0][1] + dp[d][0][1][0][0] 
                dp[d+1][0][1][1][1] += dp[d][0][1][1][1] + dp[d][0][1][1][0] 
            else:
                dp[d+1][1][0][0][1] += dp[d][1][0][0][1] + dp[d][1][0][0][0] 
                dp[d+1][1][0][1][1] += dp[d][1][0][1][1] + dp[d][1][0][1][0] 
                dp[d+1][1][1][0][1] += dp[d][1][1][0][1] + dp[d][1][1][0][0] 
                dp[d+1][1][1][1][1] += dp[d][1][1][1][1] + dp[d][1][1][1][0] 
        else:
            pass
print(dp)
print(dp[-1][1][1][1][1] + dp[-1][0][1][1][1])

# ABC114

N = int(input())
def dfs(num, use):
    if num > N:
        return 0
    cnt = 1 if use == 0b111 else 0
    cnt += dfs(num*10 + 3, use | 0b001)
    cnt += dfs(num*10 + 5, use | 0b010)
    cnt += dfs(num*10 + 7, use | 0b100)
    return cnt
ans = dfs(0, 0)
print(ans)

Verdicts: Wrong Answer

Accepted