Problem:


Score : 300 points

Problem Statement

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.

Constraints

1 \leq N < 10^9

N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

Print the number of the Shichi-Go-San numbers between 1 and N (inclusive).

Sample Input 1

575

Sample Output 1

4

There are four Shichi-Go-San numbers not greater than 575: 357, 375, 537 and 573.

Sample Input 2

3600

Sample Output 2

13

There are 13 Shichi-Go-San numbers not greater than 3600: the above four numbers, 735, 753, 3357, 3375, 3537, 3557, 3573, 3575 and 3577.

Sample Input 3

999999999

Sample Output 3

26484



Sample input:
575


Sample output:
4

Submission status: Wrong Answer

Solution code:
from itertools import product

N = int(input())

_357 = {'3', '5', '7'}

ans = 0
for r in range(3, len(str(N)) + 1):
    for numbers in product(('3', '5', '7'), repeat=r):
        if set(numbers) == _357 and int(''.join(numbers)) <= N:
            print(''.join(numbers))
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product

N = int(input())

_357 = {'3', '5', '7'}

ans = 0
continuous = True
for r in range(3, 10 + 1):
    if r > len(str(N)):
        break
    for numbers in product(('3', '5', '7'), repeat=r):
        if int(''.join(numbers)) >= N:
            continue
        if set(numbers) == _357:
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product

N = int(input())

ans = 0
for r in range(3, 10 + 1):
    for numbers in product(('3', '5', '7'), repeat=r):
        if int(''.join(numbers)) >= N:
            break
        if '3' in numbers and '5' in numbers and '7' in numbers:
            ans += 1
    else:
        continue
    break

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

ans = 0
if len(str(N))<= 2:
    ans = 0
else:
  for i in range(356, N+1):
    if "5" in str(i) and "3" in str(i) and "7" in str(i):
      ans += 1


print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = 0
for i in range(356, N+1):
    if "5" in str(i) and "3" in str(i) and "7" in str(i):
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product

n = int(input())

tfs = set()
for i in range(1,10):
    tfs |= set(product(['3', '5', '7'], repeat=i))

cnt = 0
for l in tfs:
    if ('3' in l) and ('5' in l) and ('7' in l): 
        num = int(''.join(l))
        if num <= n:
            print(num)
            cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
from itertools import product
n = int(input())
ans = 0
S = []
for i in range(10):
    S += list(product('357',repeat=i))#全部列挙
for s  in S:
    if len(set(s))>2 and int("".join(s)) < n:
        ans +=1
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
import sys
sys.setrecursionlimit(10**6)
dd = collections.defaultdict(int)
def dfs(i,n):
    if(i<n):
        k = [0,0,0]
        for j in range(len(str(i))):
            if(int(str(i)[j])==3):
                k[0]=1
            if(int(str(i)[j])==5):
                k[1]=1
            if(int(str(i)[j])==7):
                k[2]=1
        if 0 not in k:
            dd[i]+=1
        dfs(int(str(i)+"3"),n)
        dfs(int(str(i)+"5"),n)
        dfs(int(str(i)+"7"),n)


def main():
    n = int(input())
    res = 0
    a = [3,5,7]
    for i in a:
        dfs(i,n)
    for key in dd.keys():
        res+=1
    print(res)
    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
tmp = input()
nx = int(tmp)

cnt = 0
for i in range(100, nx):
    n = str(i)
    if n[0] == "3" or n[0] == "5" or n[0] == "7":
        if n[1] == "3" or n[1] == "5" or n[1] == "7":
            if n[2] == "3" or n[2] == "5" or n[2] == "7":
                flag = 0
                t = str(i)
                while i>0:
                    if i % 10 == 3 or i % 10 == 5 or i % 10 == 7:
                        flag = 1
                        i //= 10
                    else:
                        flag = 0
                        break
                
                if flag:
                    if "7" in t and "5" in t and "3" in t:
                        cnt +=1
                    
            else:
                continue
                    
                        
            
        else:
            continue
    
    else:
        continue
            
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
num753 = set()
q = deque([3,5,7])

#753数(準753も含む)の全列挙
while q:

    #右端の値を取り出す
    x = q.pop()

    #xが10**9以上になったら終了
    if x <= 10**9:

        #集合型のnum753にxを追加
        num753.add(x)

        #xを10倍して7,5,3をそれぞれ足した数をキューに追加
        q.append(x*10+3)
        q.append(x*10+5)
        q.append(x*10+7)
count = 0

#num753に格納してある値からn以下の753数を判定
for i in num753:
    if i <= n:
        lst = list(str(i))
        print(lst)
        if "3" in lst and "5" in lst and "7" in lst:
            count += 1
            
print(count)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from itertools import product

N = int(input())

q = ["3", "5", "7"]
ans = 0
while q:
    now = q.pop(0)
    if int(now) <= N:
        for i in ("3", "5", "7"):
            q.append(i + now)
            q.append(now + i)
        if len(set(now)) == 3:
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from itertools import permutations

N = int(input())

queue = []

# initial setting
for c in permutations([3, 5, 7]):
    heappush(queue, c[0]*100 + c[1]*10 + c[2])

ans = 0
while (queue):
    now = heappop(queue)
    if now <= N:
        print(now)
        ans += 1
        for i in (3, 5, 7):
            heappush(queue, now*10 + i)  # 357 -> 3573
            heappush(queue, now + i*pow(10, len(str(now))))  # 357 -> 3357

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappush, heappop
from itertools import permutations

N = int(input())

queue = []

# initial setting
for c in permutations([3, 5, 7]):
    heappush(queue, c[0]*100 + c[1]*10 + c[2])

ans = 0
while (queue):
    now = heappop(queue)
    if now <= N:
        ans += 1
    for i in (3, 5, 7):
        if now*10 + i <= N:
            heappush(queue, now*10 + i)

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heapify, heappush, heappop

N = int(input())

queue = [3, 5, 7]
heapify(queue)

ans = 0
while (queue):
    now = heappop(queue)
    ans += 1
    for i in (3, 5, 7):
        if now*10 + i <= N:
            heappush(queue, now*10 + i)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

ans = []
def dfs(a,m):
    global ans
    if len(a) == m:
        s = ""
        for i in range(m):
            s += str(a[i])
        if "7" in s and "5" in s and "3" in s:
            ans.append(int(s))
        return
    for i in [3,5,7]:
        a.append(i)
        dfs(a,m)
        a.pop()
if __name__ == "__main__":
    n = int(input())
    m = len(str(n))
    a = []
    for i in range(3,m+1):
        dfs(a,i)
    ans.sort()
    cnt = 0
    for i in range(len(ans)):
        if ans[i] < n:
            cnt+=1
    print(cnt)

Submission status: Wrong Answer

Solution code:
import queue

n=int(input())

q=queue.Queue()

q.put(3)
q.put(5)
q.put(7)

c=0
num=q.get()
while num<n:
    if "3" in str(num) and "5" in str(num) and "7" in str(num):
        c+=1
    q.put(num*10+3)
    q.put(num*10+5)
    q.put(num*10+7)
    num=q.get()

print(c)

Submission status: Wrong Answer

Solution code:
import queue

n=int(input())

q=queue.Queue()

q.put(3)
q.put(5)
q.put(7)

c=0
num=0
while num<=n:
    num=q.get()
    if "3" in str(num) and "5" in str(num) and "7" in str(num):
        c+=1
    q.put(num*10+3)
    q.put(num*10+5)
    q.put(num*10+7)

print(c)

Submission status: Wrong Answer

Solution code:
import queue

n=int(input())

q=queue.Queue()

q.put(3)
q.put(5)
q.put(7)

c=0
num=0
while num<n:
    num=q.get()
    if "3" in str(num) and "5" in str(num) and "7" in str(num):
        c+=1
    q.put(num*10+3)
    q.put(num*10+5)
    q.put(num*10+7)

print(c)

Submission status: Wrong Answer

Solution code:
cnt = 0

def main():
    n = int(input())
    m = len(str(n))
    nl = len(str(n))

    def cal(A):
        l = len(A) - 1
        ans = 0
        for idx, i in enumerate(A):
            ans += i*10**(l - idx)
        return ans

    def dfs(A):
        global cnt
        if len(A) == m:
            if len(list(set(A) & set([3, 5, 7]))) == 3:
                if (cal(A)) <= n:
                    print(cal(A))
                    cnt += 1
            return
        for i in (3, 5, 7):
            A.append(i)
            dfs(A)
            A.pop()
    for m in range(nl+1):
         dfs([])
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
cnt = 0

def main():
    n = int(input())
    m = len(str(n))
    nl = len(str(n))

    def cal(A):
        l = len(A) - 1
        ans = 0
        for idx, i in enumerate(A):
            ans += i*10**(l - idx)
        return ans

    def dfs(A):
        global cnt
        if len(A) == m:
            if len(list(set(A) & set([3, 5, 7]))) == 3:
                if (cal(A)) < n:
                    # print(cal(A))
                    cnt += 1
            return
        for i in (3, 5, 7):
            A.append(i)
            dfs(A)
            A.pop()
    for m in range(nl+1):
         dfs([])
    print(cnt)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import product
from bisect import bisect_left

n = int(input())
s = []
for i in range(3, 10):
    for v in product('753', repeat=i):
        if len(set(v)) >= 3:
            s.append(int(''.join(v)))

s.sort()

idx = bisect_left(s, n)
print(len(s[:idx]))

Submission status: Wrong Answer

Solution code:
n = input()
t = ["3","5","7"]
for i in range(8):
    s = []
    for j in t:
        s.append(j+"3")
        s.append(j+"5")
        s.append(j+"7")
    t += s
t = set(t)
t = list(t)
t.sort()
count = 0
for i in range(len(t)):
    if len(t[i]) > len(n):
        break
    if int(t[i]) > int(n):
        continue
    if '3' in t[i] and '5' in t[i] and '7' in t[i]:
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
q = deque(['3','5','7'])
ans = 0
while True:
    v = q.popleft()
    if '3' in v and '5' in v and '7' in v:
        ans += 1
    if int(v) >= n:
        print(ans)
        exit() 
    q.append(v+'3')
    q.append(v+'5')
    q.append(v+'7')

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
q = deque(['3','5','7'])
ans = 0
while True:
    v = q.popleft()
    if int(v) >= n:
        print(ans)
        exit() 
    if '3' in v and '5' in v and '7' in v:
        ans += 1
    q.append(v+'3')
    q.append(v+'5')
    q.append(v+'7')

Submission status: Wrong Answer

Solution code:
import bisect
n = int(input())
l = len(str(n))

ary = []

siti = ["3","5","7"]
def dfs (s,t):
	if len(s) == t:
		if s.count("3") > 0 and s.count("5") > 0 and s.count("7") > 0:
			ary.append(int(s))
		return
	for j in siti:
		dfs(s+j,t)

for i in range(3,l+1):
	dfs("",i)

ary.sort()
print (bisect.bisect_left(ary,n))

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect

MAX_LIM = 10**9
N = (input())
keta = len(N)
N = int(N)

print(pow(3, 9))
keta_lis = {1: [3, 5, 7], 2: [], 3: [],
            4: [], 5: [], 6: [], 7: [], 8: [], 9: []}
for i in range(1, keta):
    times = pow(10, i)
    for tmp in keta_lis[i]:
        for num in [3, 5, 7]:
            keta_lis[i+1].append(tmp + times*num)
ans = []
for keta in keta_lis.keys():
    ans.extend(keta_lis[keta])
ans = np.array(sorted(ans))
ans = ans[357 <= ans]
ans = ans[ans <= N]
count = 0
for ans_ in ans:
    if (('3' in str(ans_)) and ('5' in str(ans_)) and ('7' in str(ans_))):
        # print(ans_)
        count += 1
print(count)

# print(ans[357 <= ans])

Submission status: Wrong Answer

Solution code:
n = int(input())
ans=0
def dfs(A):
    global ans
    if len(A) > len(str(n)):
        return
    # 七五三がすべてつかわれているか?
    if not (set(A) ^ set('357')) and int(''.join(A)) < n:
        ans+=1
    for v in '357':
        A.append(v)
        dfs(A)
        A.pop()
dfs([])
print(ans)

Submission status: Wrong Answer

Solution code:
N = [int(x) for x in list(input())] # 例："1234" → [0, 1, 2, 3, 4]

def dfs(L):
    global N
    if len(L) == len(N):
        if L.count(7) > 0 and L.count(5) > 0 and L.count(3) > 0:
            return 1
        else:
            return 0

    ans = 0
    if len(L) == 0 or L[-1] == 0:
        ans += dfs(L + [0])
    for j in [3, 5, 7]:
        ans += dfs(L + [j])
    return ans

print(dfs([]))

Submission status: Wrong Answer

Solution code:
N = [0] + [int(x) for x in list(input())] # 例："1234" → [0, 1, 2, 3, 4]

def dfs(L):
    global N
    if len(L) == len(N):
        if L.count(7) > 0 and L.count(5) > 0 and L.count(3) > 0:
            return 1
        else:
            return 0

    i = len(L) - 1  # Lの右端の桁
    ans = 0
    if L[i] == N[i]:    # Lの0, 1, .., i桁がNの0, 1, ..., i桁と同じ
        next = []
        if i == 0:  # L[i]はダミーの0
            for j in [0, 3, 5, 7]:
                if j <= N[i + 1]:
                    next.append(j)
        else:
            for j in [3, 5, 7]:
                if j <= N[i + 1]:
                    next.append(j)
    elif L[i] == 0:
        next = [0, 3, 5, 7]
    else:
        next = [3, 5, 7]

    for j in next:
        ans += dfs(L + [j])

    return ans

print(dfs([0]))

Submission status: Wrong Answer

Solution code:
N = [0] + [int(x) for x in list(input())] # 例："1234" → [0, 1, 2, 3, 4]
print(N)

def dfs(L):
    global N
    if len(L) == len(N):
        if L.count(7) > 0 and L.count(5) > 0 and L.count(3) > 0:
            return 1
        else:
            return 0

    i = len(L) - 1  # Lの右端の桁
    ans = 0
    if L[i] == N[i]:    # Lの0, 1, .., i桁がNの0, 1, ..., i桁と同じ
        next = []
        if i == 0:  # L[i]はダミーの0
            for j in [0, 3, 5, 7]:
                if j <= N[i + 1]:
                    next.append(j)
        else:
            for j in [3, 5, 7]:
                if j <= N[i + 1]:
                    next.append(j)
    elif L[i] == 0:
        next = [0, 3, 5, 7]
    else:
        next = [3, 5, 7]

    for j in next:
        ans += dfs(L + [j])

    return ans

print(dfs([0]))

Submission status: Wrong Answer

Solution code:
N = input()
L = len(N)
dp = [[[[[0]*2 for _ in range(2)] for _ in range(2)] for _ in range(2)] for _ in range(L+1)]
dp[0][0][0][0][0] = 1
# dp[i][j][k][l][m]: iは桁数、j,k,lは3, 5, 7が一回以上でたかどうか、mは未満フラグ(未満ならば1)


for i in range(L):
    n = int(N[i])
    for j in range(2): #3
        for k in range(2): #5
            for l in range(2): #7
                for smaller in range(2):
                    for a in [0, 3, 5, 7]:
                        nj, nk, nl, ns = j, k, l, 1
                        if i > 0 and a == 0:
                            continue
                        if smaller==0 and n < a:
                            continue
                        if smaller==0 and n == a:
                            ns = 0
                        elif smaller == 0 and n > a:
                            ns = 1
                        
                        if a == 3:
                            nj = 1
                        elif a == 5:
                            nk = 1
                        elif a == 7:
                            nl = 1
                        else:
                            pass

                        dp[i+1][nj][nk][nl][ns] += dp[i][j][k][l][smaller]

print(sum(dp[L][1][1][1]))

Submission status: Wrong Answer

Solution code:
n = input()
dp = [[0]*8 for _ in range(2)]
if int(n[0])==3:
    dp[0][4] = 1
if int(n[0])==5:
    dp[0][2] = 1
if int(n[0])==7:
    dp[0][1] = 1
if int(n[0])>3:
    dp[0][4] = 1
if int(n[0])>5:
    dp[0][2] = 1
if int(n[0])>7:
    dp[0][1] = 1
for i in range(1, len(n)):
    newdp = [[0]*8 for _ in range(2)]
    if n[i]=='3':
        newdp[0][4] = dp[0][4]
        newdp[0][5] = dp[0][1] + dp[0][5]
        newdp[0][6] = dp[0][2] + dp[0][6]
        newdp[0][7] = dp[0][3] + dp[0][7]
    elif n[i]=='5':
        newdp[0][2] = dp[0][2]
        newdp[0][3] = dp[0][1] + dp[0][3]
        newdp[0][6] = dp[0][4] + dp[0][6]
        newdp[0][7] = dp[0][5] + dp[0][7]
    elif n[i]=='7':
        newdp[0][1] = dp[0][1]
        newdp[0][3] = dp[0][2] + dp[0][3]
        newdp[0][5] = dp[0][4] + dp[0][5]
        newdp[0][7] = dp[0][6] + dp[0][7]
    newdp[1][1] = dp[1][1] + dp[0][1]*(int(n[i])>7) + 1
    newdp[1][2] = dp[1][2] + dp[0][2]*(int(n[i])>5) + 1
    newdp[1][4] = dp[1][4] + dp[0][4]*(int(n[i])>3) + 1
    newdp[1][3] = dp[1][1] + dp[1][2] + dp[1][3]*2 + (dp[0][1] + dp[0][3])*(int(n[i])>5) + (dp[0][2] + dp[0][3])*(int(n[i])>7)
    newdp[1][5] = dp[1][1] + dp[1][4] + dp[1][5]*2 + (dp[0][1] + dp[0][5])*(int(n[i])>3) + (dp[0][4] + dp[0][5])*(int(n[i])>7)
    newdp[1][6] = dp[1][2] + dp[1][4] + dp[1][6]*2 + (dp[0][2] + dp[0][6])*(int(n[i])>3) + (dp[0][4] + dp[0][6])*(int(n[i])>5)
    newdp[1][7] = dp[1][3] + dp[1][5] + dp[1][6] + dp[1][7]*3 + (dp[0][3]+ dp[0][7])*(int(n[i])>3) + (dp[0][5]+ dp[0][7])*(int(n[i])>5) + (dp[0][6]+ dp[0][7])*(int(n[i])>7)
    dp = newdp
print(dp[0][7]+dp[1][7])

Submission status: Wrong Answer

Solution code:
import itertools
import bisect
n=int(input())
lst=[]
for i in range(357, n+1):
  temp=list(str(i))
  if "3" in temp and "5" in temp and "7" in temp:
    lst.append(i)
print(len(lst))

Submission status: Wrong Answer

Solution code:
import itertools
import collections
n=int(input())
l=len(str(n))
cnt=0
if l<3:
  print(0)
  exit()
for i in range(3,l+1):
  for k in itertools.product(['7','5','3'],repeat=i):
    j=int(''.join(k))
    c=collections.Counter(k)
    cv=c.values()
    if all(vv!=0 for vv in cv) and j<=n:
      cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
import itertools
import collections
n=int(input())
l=len(str(n))
cnt=0
if l<3:
  print(0)
  exit()
for i in range(3,l):
  for k in itertools.product(['7','5','3'],repeat=i):
    j=int(''.join(k))
    c=collections.Counter(k)
    cv=c.values()
    if all(vv!=0 for vv in cv) and j<=n:
      cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=len(str(n))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-

from collections import deque

N = int(input())

item = ["3","5","7"]

d = deque([])
Order = 3
for _ in range(0,Order):
    d.append(item[0])

cand = []
cand.append("".join(list(d)))

while True:

    if d == deque([]):
        Order += 1
        for _ in range(0,Order):
            d.append(item[0])

    now = d.pop()

    if now == item[0]:
        d.append(item[1])
        while len(d) < Order:
            d.append(item[0])
        cand.append("".join(list(d)))
#        print("".join(list(d)))
    elif now == item[1]:
        d.append(item[2])
        while len(d) < Order:
            d.append(item[0])
        cand.append("".join(list(d)))
#        print("".join(list(d)))
    elif now == item[2]:
        continue

    # 終了条件
    if int("".join(list(d))) > N:
        break

cnt = 0
for Num in cand:
    if Num.count("3") != 0 and Num.count("5") != 0 and Num.count("7") != 0:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
import itertools as it
n = int(input())
l = len(str(n))

res = []
for i in range(3, l + 1):
    for gen in it.product("357", repeat=i):
        gen_s = "".join(gen)
        if int(gen_s) < n:
            res.append(gen_s)

cnt = 0
for r in res:
    if all(r.count(c) for c in "357"):
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())

que=deque([3,5,7])
x=0
ans=0
while x<=n:
    x=que.popleft()
    s=str(x)
    if s.count('3')>0 and s.count('5')>0 and s.count('7')>0:
        ans+=1
    que.append(10*x+3)
    que.append(10*x+5)
    que.append(10*x+7)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

ans = 0
def dfs(s):
    global ans
    if int(s) > N:
        return
    if all(s.count(i) for i in '753'):
        ans += 1
        return
    for c in '753':
        dfs(s+c)
        
dfs('0')
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


# ワーシャルフロイド (任意の2頂点の対に対して最短経路を求める)
# 計算量n^3 (nは頂点の数)
def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定



# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
# def dfs(cnt, ret, n, m):
#     if cnt == m:
#         cnt7 = 0
#         cnt5 = 0
#         cnt3 = 0
#         for i in ret:
#             if i == "7":
#                 cnt7 += 1
#             elif i == "5":
#                 cnt5 += 1
#             else:
#                 cnt3 += 1
#         if cnt7 == 0 or cnt5 == 0 or cnt3 == 0:
#             return
#         if int(ret) <= n:
#             global ans
#             ans += 1
#             return
#     return dfs(cnt + 1, ret + "3", n, m)



n = int(input())
m = len(str(n)) 
# print(n, m)
# print("m =", m)
x = [0 for i in range(9)]
for i in range(3, 9):
    x[i] = i * (i - 1) * (i - 2) * (3 ** (i - 3))
# print("x =", x)

ans = 0
for i in range(m):
    ans += x[i]

def dfs(cnt, ret, n, m):
    if cnt == m:
        # print("ret =", ret)
        cnt7 = 0
        cnt5 = 0
        cnt3 = 0
        for i in ret:
            if i == "7":
                cnt7 += 1
            elif i == "5":
                cnt5 += 1
            else:
                cnt3 += 1
        if cnt7 == 0 or cnt5 == 0 or cnt3 == 0:
            return
        if int(ret) <= n:
            global ans
            ans += 1
        return
    dfs(cnt + 1, ret + "7", n, m)
    dfs(cnt + 1, ret + "5", n, m)
    dfs(cnt + 1, ret + "3", n, m)
    return 

dfs(0, "", n, m)

print(int(ans))

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


# ワーシャルフロイド (任意の2頂点の対に対して最短経路を求める)
# 計算量n^3 (nは頂点の数)
def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定



# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
# def dfs(cnt, ret, n, m):
#     if cnt == m:
#         cnt7 = 0
#         cnt5 = 0
#         cnt3 = 0
#         for i in ret:
#             if i == "7":
#                 cnt7 += 1
#             elif i == "5":
#                 cnt5 += 1
#             else:
#                 cnt3 += 1
#         if cnt7 == 0 or cnt5 == 0 or cnt3 == 0:
#             return
#         if int(ret) <= n:
#             global ans
#             ans += 1
#             return
#     return dfs(cnt + 1, ret + "3", n, m)



n = int(input())
m = len(str(n)) 
# print(n, m)
# print("m =", m)
x = [0 for i in range(9)]
for i in range(3, 9):
    x[i] = i * (i - 1) * (i - 2) * (3 ** (i - 3))
# print("x =", x)
ans = (m - 1) * (m - 2) * (m - 3) * (3 ** (m - 4))

def dfs(cnt, ret, n, m):
    if cnt == m:
        # print("ret =", ret)
        cnt7 = 0
        cnt5 = 0
        cnt3 = 0
        for i in ret:
            if i == "7":
                cnt7 += 1
            elif i == "5":
                cnt5 += 1
            else:
                cnt3 += 1
        if cnt7 == 0 or cnt5 == 0 or cnt3 == 0:
            return
        if int(ret) <= n:
            global ans
            ans += 1
        return
    dfs(cnt + 1, ret + "7", n, m)
    dfs(cnt + 1, ret + "5", n, m)
    dfs(cnt + 1, ret + "3", n, m)
    return 

dfs(0, "", n, m)

print(int(ans))