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: Accepted

Solution code:
import itertools

n = int(input())

products = []
for i in range(3, len(str(n)) + 1):
    tmp = list(itertools.product(['3', '5', '7'], repeat = i))
    tmp2 = list(map(''.join, tmp))
    tmp3 = list(map(int, tmp2))
    tmp4 = [j for j in tmp3 if j <= n]
    products = products + tmp4

out = 0
for p in products:
    str_p = str(p)
    if ('3' in str_p) and ('5' in str_p) and ('7' in str_p):
        out += 1
print(out)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    L = len(str(N))
    cand = []
    def dfs(s,N,cand):
        if s != '' and int(s) > N:
            return
        
        for i in ['3','5','7']:
            tmp = s + i
            if int(tmp) <= N:
                cand.append(tmp)
            dfs(tmp,N,cand)
    
    dfs('',N,cand)
    ans = 0
    for c in cand:
        if c.count('3') >= 1 and c.count('5') >= 1  and c.count('7') >= 1:
            ans += 1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import product
NS = input()
N =int(NS)

def iter_p_adic(n):
    from itertools import product
    tmp = [('3','5','7')] * n
    return product(*tmp)
ans = 0
for k in range(3,len(NS)+1):
    for i in iter_p_adic(k):
        ls = list(i)
        if ls.count('3') > 0 and ls.count('5') > 0 and ls.count('7') > 0 and int(''.join(ls)) <= N:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

def dfs(x):
  if x != '' and n < int(x):
    return 0
  if set(x) == {'3','5','7'}:
    c = 1
  else:
    c = 0
  for i in '357':
    c += dfs(x+i)
  return c

print(dfs(''))

Submission status: Accepted

Solution code:
N=int(input())
A=['3','5','7']
i=0
while 1:
    now=A[i]
    if int(now+'3')<=N:A.append(now+'3')
    if int(now+'5')<=N:A.append(now+'5')
    if int(now+'7')<=N:A.append(now+'7')
    else:break
    i+=1

ans=0
B={'3','5','7'}
for a in A:
    if set(list(a))&B==B:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())


def conv3570(p):
  D = [0, 3, 5, 7]
  ans = 0
  i = 0
  while p > 0:
    ans += D[p % 4] * 10**i
    p //= 4
    i += 1
  return ans

p = 0
q = 0
ans = 0
while q <= N:
  q_str = str(q)
  if q_str.count("0") == 0 and q_str.count("3") > 0 and q_str.count("5") > 0 and q_str.count("7") > 0:
    ans += 1
  p += 1
  q = conv3570(p)
  
print(ans)

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

import string

def main():
    N = i_input()
    k = len(str(N))
    ans = 0
    l = []
    def rec(n,k):
        k += 1
        if int(n) > N:
            return
        if "3" in n and "5" in n and "7" in n:
            l.append(int(n))
        rec(n+"3",k)
        rec(n+"5",k)
        rec(n+"7",k)
    rec("0",0)
    print(len(l))





if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
T = ("3","5","7")

def dfs(x):
  if x != "" and int(x) > N:
    return 0
  res = 0
  if len(set(x)) == 3:
    res = 1
  for t in T:
    res += dfs(x + t)
  return res
  
print(dfs(""))

Submission status: Accepted

Solution code:
N = int(input())
T = ("3","5","7")

from collections import deque
que = deque(list(T))

ans = 0
while que:
  num = que.pop()
  if int(num) > N:
    continue
  if len(set(num)) == 3:
    ans += 1
  for t in T:
    que.append(num + t)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
T = ("3","5","7")

from collections import deque
que = deque(list(T))

ans = 0
while que:
  num = que.popleft()
  if int(num) > N:
    continue
  if len(set(num)) == 3:
    ans += 1
  for t in T:
    que.append(num + t)

print(ans)

Submission status: Accepted

Solution code:
N = input()
digit = len(N)

N = int(N)

import itertools

ans = 0
for i in range(1, digit + 1):
  for prod in itertools.product(("3","5","7"), repeat = i):
    if int("".join(prod)) <= N and len(set(prod)) == 3:
      ans += 1

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
s=len(str(N))

ans=0
import itertools
b1=list(itertools.product("0357", repeat=s))
for k in b1:
    t=int(''.join(k))
    if N<t:break
    x=set(str(t))
    y=x-{'3','5','7'}
    if len(y)==0 and len(x-y)==3:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
# A=[3,5,7]
n=int(input())
def dfs(s):
    if int(s)>n:
        return 0
    cnt=0
    if all(i in s for   i in "357"):
        cnt=1
    for i in "357":
        cnt+= dfs(s+i)
    return cnt 
print(dfs("0"))

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
S = deque([3, 5, 7])
ans = 0
for _ in range(3**10):
    a = S.popleft()
    if a <= N:
        tmp = a
        j3, j5, j7 = False, False, False
        while tmp > 0:
            if tmp%10 == 3:
                j3 = True
            elif tmp%10 == 5:
                j5 = True
            else:
                j7 = True
            tmp //= 10
        if j3 and j5 and j7:
            ans += 1
    S.append(a*10+3)
    S.append(a*10+5)
    S.append(a*10+7)
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
idx = 0

ans = 0
def dfs(idx, st):
    global ans
    if idx==10:
        return
    if int(st)>N:
        return
    elif len(set(st))>=3:
        ans += 1
    for nx in ('3', '5', '7'):
        dfs(idx+1, st+nx)

for nx in ('3', '5', '7'):
    dfs(1, nx)
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
n = int(input())
m = len(str(n))
ans = 0
for i in range(3,m+1):
    l = list(product('753',repeat=i))
    for _ in l:
        x = ''.join(list(_))
        if '7' in x and '5' in x and '3' in x:
            if n >= int(x):
                ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
N = str(input())
Keta = len(N)
N_List = ["3","5","7"]

## ここまでの計算量はMax8回とみてOK？
## いずれにしろあまり気にしなくてOK
Ans = 0
for i in range(3,Keta):
    Ans += 3**i
    Ans -= (2**i*3) -3

N = int(N)

##　組み合わせはMaxでも3**10 = 60000くらい
##  計算量間に合う
if Keta >= 3:
    for Moji in itertools.product(N_List, repeat=Keta):
        Moji_Kazu = len(set(Moji))
        Str_Number = int("".join(Moji))
        if (Str_Number <= N) & (Moji_Kazu == 3):
            Ans += 1
    
print(Ans)

Submission status: Accepted

Solution code:
import itertools
N = int(input())
cnt = 0
for i in range(3, len(str(N))+1):
    for j in list(itertools.product('357', repeat = i)):
        if ('3' in j) & ('5' in j) & ('7' in j):
            if int(''.join(j)) <= N:
                cnt += 1
            else:
                break
print(cnt)