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:
hutamoji_list=[[None]*11 for i in range(3)]#35,37,57の順
def hutamoji(keta,one,two):
    global hutamoji_list
    if one*two==15:
        index=0
    elif one*two==21:
        index=1
    else:
        index=2
    if hutamoji_list[index][keta]!=None:
        return hutamoji_list[index][keta]
    ans=[]
    if keta==1:
        return ans
    for each in hutamoji(keta-1,one,two):
        ans.append(one*(10**(keta-1))+each)
        ans.append(two * (10 ** (keta - 1)) + each)
    for i in [one,two]:
        for j in [one,two]:
            if i!=j:
                ans.append(i*(10**(keta-1))+int(str(j)*(keta-1)))
    ans.sort()
    hutamoji_list[index][keta]=ans

    return ans


def sannmoji(keta):
    hitigosan=[3,5,7]
    ans=[]
    if keta<=2:
        return ans
    for each in sannmoji(keta-1):
        for i in [3,5,7]:
            ans.append(i*(10**(keta-1))+each)
    for one,two,three in [[3,5,7],[5,3,7],[7,3,5]]:
        hutas=hutamoji(keta-1,two,three)
        for huta in hutas:
            ans.append(one*(10**(keta-1))+huta)
    ans.sort()
    return ans


sannmoji(10)
n=input()
keta=len(n)
n=int(n)
ans=0
for i in range(1,keta):
    ans+=len(sannmoji(i))

for i in sannmoji(keta):
    if i <=n:
        ans+=1
    else:
        break
print(ans)

Submission status: Accepted

Solution code:
N = None
K = None
cnt = 0 

def rec(num_str):
    global N, K, cnt
    if len(num_str) > K:
        return
    if '7' in list(num_str) and '5' in list(num_str) and '3' in list(num_str):
        if int(num_str) <= N:
           cnt += 1
    rec(num_str+'7') 
    rec(num_str+'5') 
    rec(num_str+'3') 


if __name__ == '__main__':
    S = input()
    N = int(S)
    K = len(S)
    rec('')
    print(cnt)

Submission status: Accepted

Solution code:
import itertools

N = input()

if len(N)<=2:
    print(0)
    exit()
product_list = []
for i in range(3,len(N)+1):
    product_list += list(itertools.product('753',repeat=i))
#print(product_list)
res = 0

for i in product_list:
    num = ''.join(list(i))
    if int(N) < int(num):
        continue
    if num.count('5')>0 and num.count('7')>0 and num.count('3')>0:
        res += 1
print(res)

Submission status: Accepted

Solution code:
import itertools

N = input()
N_len = len(N)
N_int = int(N)
ans = 0
for i in range(3, 10):
    target = list(itertools.product([3, 5, 7], repeat=i))
    for t in target:
        s = ''.join(map(str, t))
        a = int(s)
        if a <= N_int and s.count('3') and s.count('5') and s.count('7'):
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
 
 
def main():
    n = input()
    print(sev(n))
 
 
def sev(n: str) -> int:
    ret = 0
    d = len(n)
    while d > 2:
        for comb in itertools.product(['3', '5', '7'], repeat=d):
            s = ''.join(comb)
            if '3' in comb and '5' in comb and '7' in comb and int(s) <= int(n):
                ret += 1
        d -= 1
    return ret
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools


def main():
    n = input()
    print(sev(n))


def sev(n: str) -> int:
    ret = 0
    d = len(n)
    while d > 2:
        for comb in itertools.product(['3', '5', '7'], repeat=d):
            s = ''.join(comb)
            if '3' in s and '5' in s and '7' in s and int(s) <= int(n):
                ret += 1
        d -= 1
    return ret


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_right
from itertools import product


def bisectsearch_right(L, a):
    i = bisect_right(L, a)
    return(i)


N = input()
d = len(N)
N = int(N)
a = [0]*d
for i in range(1, d):
    a[i] = 3**i-3*2**i+3
# print(a)
S = {3, 5, 7}

L = set()
for k in product(S, repeat=d):
    l = set(k)
    if S == l:
        t = [None]*d
        for i in range(d):
            t[i] = str(k[i])
        L.add(int(''.join(t)))
# print(L)
L = list(L)
L.sort()
ct = bisectsearch_right(L, N)
print(sum(a)+ct)

Submission status: Accepted

Solution code:
from collections import deque
import bisect
n=int(input())
sft=deque()
x=deque([3,5,7])
while x:
    a=x.popleft()
    if 100<=a<=777:
        sft.append(a)
    else:
        x.append(a*10+3)
        x.append(a*10+5)
        x.append(a*10+7)
ans=[]
for i in range(3**11):
    a=sft.popleft()
    ans.append(a)
    sft.append(a*10+3)
    sft.append(a*10+5)
    sft.append(a*10+7)
count=0
for i in ans:
    if n<i:
        print(count)
        break
    else:
        ss=str(i)
        if "3" in ss and "5" in ss and "7" in ss:
            count+=1

Submission status: Accepted

Solution code:
N = int(input())

def dfs(n):
  if int(n) > N:
    return 0
  if ('3' in n) and ('5' in n) and ('7' in n):
    ret = 1
  else:
    ret = 0
  for c in '357':
    ret += dfs(n+c)
  return ret

print(dfs('0'))

Submission status: Accepted

Solution code:

N = int(input())


def dfs(s):
    if int(s) > N:
        return 0

    res = 1 if all(s.count(c) > 0 for c in "357") else 0
    for c in "357":
        res += dfs(s + c)
    return res


print(dfs("0"))

Submission status: Accepted

Solution code:
N = int(input())

def DFS(s):
    if int(s) > N:
        return 0
    if "7" in s and "5" in s and "3" in s:
        ret = 1
    else:
        ret = 0
    for c in "753":
        ret += DFS(s + c)
    return ret

print(DFS("0"))

Submission status: Accepted

Solution code:
n=int(input())
que=[3,5,7]
ans=0
def dfs(s):
  global ans
  if n<s:
    return
  
  s=str(s)
  if "3" in s and "5" in s and "7" in s:
    ans+=1
  
  s=int(s)
  for i in que:
   dfs(10*s+i)
  
  return ans
print(dfs(0))

Submission status: Accepted

Solution code:
import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())

def main():
    n = II()
    def dfs(cur, use):
        counter = 0
        def dfs_(cur, use):
            nonlocal counter
            if cur > n:      return None
            if use == 0b111: counter += 1
            dfs_(cur*10 + 7, use | 0b001)
            dfs_(cur*10 + 5, use | 0b010)
            dfs_(cur*10 + 3, use | 0b100)
        dfs_(cur, use)
        return counter
    print(dfs(0, 0))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import collections

#+++++

def count_max(a_len, using):
	if a_len < 3:
		return 0
	
	total = 3 ** a_len
	
	#33...33, 55...55,77...77
	all_single = 3 - len(using)
	
	#333553535
	tt = 2 ** a_len - 2
	
	



def main():
	n = int(input())
	#b , c = map(int, input().split())
	#s = input()
	ret = 0
	q = collections.deque()
	if n < 357:
		return 0
	
	for i, v in enumerate([3,5,7]):
		q.append((v, 1, 2**i))
		
	while q:
		value, keta, is_full = q.popleft()
		#print(value,keta,is_full)
		for i, v in enumerate([3,5,7]):
			n_value = value + v*(10**keta)
			if n_value > n:
				continue
			n_is_full = is_full | (2**i)
			if n_is_full == 7:
				ret += 1
			q.append((n_value, keta+1, n_is_full))
	
	print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
nums = ['3', '5', '7']
now = ''
q = deque(nums)
ans = 0
flag = True
while flag:
    n = q.popleft()
    for num in nums:
        tmp = n
        tmp += num
        if int(tmp) > N:
            flag = False
            break
        if '3' in tmp and '5' in tmp and '7' in tmp:
            ans += 1
        q.append(tmp)

print(ans)

Submission status: Accepted

Solution code:
import bisect
a=[3,5,7]
c=[3,5,7]
for i in range(8):
    b=[]
    for j in a:
        for k in range(3):
            b.append(int(str(j)+str(k*2+3)))
            c.append(int(str(j)+str(k*2+3)))
    a=b
n=int(input())
def is755(d):
    if len(set(list(str(d))))<3:
        return False
    else:
        return True
print(sum([i<=n and is755(i) for i in c]))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

from itertools import combinations_with_replacement, permutations, product
n = int(input())
def sub(n):
    s = set()
    for nums in product(*[[3,5,7] for _ in range(n)]):
        if not all(item in nums for item in [3,5,7]):
            continue
        v = 0
        b = 1
        for c in nums:
            v += c*b
            b *= 10
        s.add(v)
    return sorted(list(s))
from bisect import bisect_right as br
l = len(str(n))
ans = 0
for i in range(1, l+1):
    ans += br(sub(i), n)
print(ans)

Submission status: Accepted

Solution code:
#C - 755
import sys
sys.setrecursionlimit(10**6)
N = input()

lis = ['3','5','7']
count = 0
def dfs(A):
    global lis
    global count
    if len(A) >= len(N):
        A_str = ''.join(A)
        A_int = int(A_str)
        N_int = int(N) 
        if N_int < A_int:
            return
    if len(set(A)) == 3:
        count += 1
    for v in range(3):
        A.append(lis[v])
        dfs(A)
        A.pop()
dfs([])    
print(count)

Submission status: Accepted

Solution code:
N = int(input())


def dfs(x):
    if int(x) > N:
        return 0

    if all(c in x for c in '357'):
        cnt = 1
    else:
        cnt = 0
    for c in '357':
        cnt += dfs(x+c)
    return cnt


print(dfs('0'))

Submission status: Accepted

Solution code:
c = [0, 3, 5, 7]


N = input()
l = len(N)
N = int(N)


def parse_to_tri(x):
    ret = 0
    d = 1
    for i in range(l):
        ret += c[x % 4]*d
        d *= 10
        x //= 4
    return ret


ans = 0


for i in range(4**l):
    x = parse_to_tri(i)
    s = str(x)
    if '3' not in s or '5' not in s or '7' not in s:
        continue
    if '0' in s:
        continue
    if x <= N:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import math
import itertools
import collections

def main():
	N = int(input())
	digit = math.floor(math.log10(N)) + 1
	if digit <= 2:
		print(0)
		return 0
	cnt = int(3 * (3 ** (digit - 1) - 2 ** (digit + 1) + 2 * digit + 1) / 2)

	num = ['3', '5', '7']
	cand = ["".join(list(x)) for x in itertools.product(num, repeat=digit)]
	for ca in cand:
		c = collections.Counter(ca)
		if c['3'] and c['5'] and c['7'] and int(ca) <= N:
			cnt += 1
	print(cnt)

main()

Submission status: Accepted

Solution code:
N = int(input())

def dfs(s):
    if int(s) > N:
        return 0

    ret = 1 if all(s.count(c) > 0 for c in '753') else 0
    for c in '753':
      ret += dfs(s + c)
    return ret

print(dfs('0'))

Submission status: Accepted

Solution code:
def f(n):
    if n==1:
        yield "7"
        yield "5"
        yield "3"
    else:
        for i in f(n-1):
            yield i+"7"
            yield i+"5"
            yield i+"3"
n=int(input())
ans=0
for j in range(1,10):
    for i in f(j):
        if len(set(i))==3 and int(i)<=n:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
from collections import Counter
N = int(input())
res = 0
for k in range(11):
    for p in product([3,5,7],repeat=k):
        if len(Counter(p)) == 3:
            tmp, pw = 0, 1
            for q in p:
                tmp += q*pw
                pw *= 10
            if tmp <= N:
                res += 1
print(res)

Submission status: Accepted

Solution code:
def digit(N, M):
    def f(j,k):
        if k==3: res = 1
        elif k==5: res = 2
        elif k==7: res = 4
        return j|res

    L = len(N)
    dp = [[[0] * M for i in range(L + 1)] for j in range(2)]

    dp[0][0][0] = 1
    for i in range(1,L):
        dp[1][i][0] = 1
    for i in range(L):
        for j in range(M):
            for k in [3,5,7]:
                if k < int(N[i]):
                    dp[1][i+1][f(j, k)] += dp[0][i][j] + dp[1][i][j]
                elif k == int(N[i]):
                    dp[0][i+1][f(j, k)] += dp[0][i][j]
                    dp[1][i+1][f(j, k)] += dp[1][i][j]
                else:
                    dp[1][i+1][f(j, k)] += dp[1][i][j]
    return dp[0][L][K] + dp[1][L][K]

###########################################################################

N = input().rstrip()
K = 7
M = K + 1                               # 状態数
print(digit(N, M))

Submission status: Accepted

Solution code:
n = input()
l = len(n)
n = int(n)
data = [['0']*l for i in range(4**l)]
for i in range(4**l):
  k = i
  for j in range(l):
    a = k//4**(l-1-j)
    if a==1:
      data[i][j]='3'
    if a==2:
      data[i][j]='5'
    if a==3:
      data[i][j]='7'
    k%=4**(l-1-j)
ans = 0
for u in data:
  num = int(''.join(u))
  if num<=n:
    num = str(num)
    if '0' not in num and '3' in num and '5' in num and '7' in num:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

n=int(input())

a=[3,5,7]

b=deque(a)

while b:
  v=b.popleft()
  
  x=v*10+3
  y=v*10+5
  z=v*10+7
  if x<=n:
    a.append(x)
    b.append(x)
    
  if y<=n:
    a.append(y)
    b.append(y)
    
  if z<=n:
    a.append(z)
    b.append(z)
ans=0    
for i in a:
  l=str(i)
  if '3' in l and '5' in l and '7' in l:
    ans+=1
    
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

ans = 0


def gen_pat(cur):
    global ans

    if int(cur) > n:
        return

    if len(set(cur)) == 4:  # 0 7 5 3 が含まれる。
        ans += 1

    gen_pat(cur + "3")
    gen_pat(cur + "5")
    gen_pat(cur + "7")


gen_pat("0")
print(ans)

Submission status: Accepted

Solution code:
import sys

N=int(input())
sys.setrecursionlimit(27000)

cnt=0
def func(n:int,x:str):
    global cnt
    cnt_3=x.count('3')
    cnt_5=x.count('5')
    cnt_7=x.count('7')
    if n<len(x):
        return 0
    if int(x)<=N and cnt_3>0 and cnt_5>0 and cnt_7>0:
        cnt+=1
    func(n,x+'3')
    func(n,x+'5')
    func(n,x+'7')

func(len(str(N)),'3')
func(len(str(N)),'5')
func(len(str(N)),'7')
print(cnt)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(4100000)
n = int(input())
numlist = [3, 5, 7]


ans = 0


def dfs(num, a, b, c):
    global ans
    if num > n:
        return False
    if a == 1 and b == 1 and c == 1:
        if num <= n:
            ans += 1
    for d in numlist:
        na, nb, nc = a, b, c
        if d == 3:
            na = 1
        if d == 5:
            nb = 1
        if d == 7:
            nc = 1
        if num == 0:
            num = d
        else:
            num = num * 10 + d
        dfs(num, na, nb, nc)
        num //= 10


dfs(0, 0, 0, 0)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

def dfs(s):
    if int(s) > n:
        return 0
    
    ret = 1 if all(s.count(c) > 0 for c in '753') else 0
    for c in '753':
        ret += dfs(s+c)
    return ret

print(dfs('0'))

Submission status: Accepted

Solution code:
#わからなかったので答えを見た
#実装の仕方や、考え方を復習してもう一回やってみる

N = int(input())

def solve(s):
    #ベースケース
    if int(s) > N:
        return 0
    #s.countでsに357のうちどれかが入っていることを確かめる 真なら1で偽なら0
    ret = 1 if all(s.count(i) > 0 for i in '357') else 0

    #再帰する
    for c in '753':
        ret += solve(s+c)

    return ret

print(solve("0"))

Submission status: Accepted

Solution code:
import itertools,bisect

num_list = []#753数となりえる数の生成
for i in range(3,10):
    num_list += list(itertools.product('753',repeat=i) )
    
num = []#753数の絞り込み
for nm in num_list:
    if '3' in nm and '5' in nm and '7' in nm:
        num.append(int(''.join(nm)))

num.sort()#にぶたん
print(bisect.bisect_right(num,int(input())))

Submission status: Accepted

Solution code:
import itertools,bisect

num_list = []
def toInt(arr):
    num = int(''.join(arr))
for i in range(3,10):
    num_list += list(itertools.product('753',repeat=i) )
num = []
for nm in num_list:
    if '3' in nm and '5' in nm and '7' in nm:
        num.append(int(''.join(nm)))
num.sort()

print(bisect.bisect_right(num,int(input())))

Submission status: Accepted

Solution code:
n = int(input())

l = []


def dfs(num: list, nset: set, depth: int):
    global l
    if depth == 0:
        #print(num, nset, depth)
        if "3" in nset and "5" in nset and "7" in nset:
            l.append(int("".join(num)))
    else:
        for c in ["3", "5", "7"]:
            _num = num.copy()
            _nset = nset.copy()
            _num.append(c)
            _nset.add(c)
            dfs(_num, _nset, depth-1)

for i in range(3,11):
    dfs([], set(), i)

ans = 0

for i in range(len(l)):
    if n >= l[i]:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

def is_753(a):
    check = {'7': 0, '5': 0, '3': 0}
    string = str(a)
    for i in range(len(str(a))):
        if not string[i] in ['7', '5', '3']:
            return False
        check[string[i]] += 1
    for v in check.values():
        if v == 0:
            return False
    return True
    

q = [3, 7, 5]
count = 0

while len(q) > 0:
    # print(q)
    front = q.pop(0)
    # print('front:', front, end=' ')
    if len(str(front)) >= 3 and is_753(front):
        count += 1
    # create next
    for i in [3, 5, 7]:
        cand = int(str(i) + str(front))
        if cand <= n:
            q.append(cand)

print(count)

Submission status: Accepted

Solution code:
# 桁DPぽいけどただの再帰でいい
n = input()


def rec(i):
    if int(i) > int(n):
        return 0
    ret = 0
    if "3" in i and "5" in i and "7" in i:
        ret += 1
    for j in ["3", "5", "7"]:
        ret += rec(i + j)
    return ret


ans = 0
for i in ["3", "5", "7"]:
    ans += rec(i)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n=int(input())
def res(v:int, all:list):
    if v>n:
        return
    if "3" in list(str(v)) and "5" in list(str(v)) and "7" in list(str(v)):
        all.append(v)
    res(10*v+3,all)
    res(10*v+5,all)
    res(10*v+7,all)
all=[]

res(3,all)
res(5,all)
res(7,all)


print(len(all))

Submission status: Accepted

Solution code:
N = int(input())

dic = [3, 5, 7]

ans = set()
def dfs(s):
    if s:
        if int(s) <= N:
            if len(set(s)) == 3:
                ans.add(s)
        else:
            return
    for c in '753':
        dfs(s+c)

dfs("")
print(len(ans))

Submission status: Accepted

Solution code:
N = int(input())

dic = [3, 5, 7]

ans = set()
def dfs(s):
    if s:
        if int(s) <= N:
            if len(set(s)) == 3:
                ans.add(s)
        else:
            return
    dfs(s+"3")
    dfs(s+"5")
    dfs(s+"7")

dfs("")
print(len(ans))

Submission status: Accepted

Solution code:
N = int(input())

dic = [3, 5, 7]

ans = list()
def dfs(s):
    if s:
        if int(s) <= N:
            if len(set(s)) == 3:
                ans.append(s)
        else:
            return
    dfs(s+"3")
    dfs(s+"5")
    dfs(s+"7")

dfs("")
print(len(ans))

Submission status: Accepted

Solution code:
n=int(input())

def dfs(s):
  if s!="" and int(s)>n:
    return 0
  
  if len(set(list(s)))<3:
    ret=0
  else:
    ret=1
  
  for i in "753":
    ret+=dfs(s+i)
  
  return ret

print(dfs(""))

Submission status: Accepted

Solution code:
N = int(input())

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

Submission status: Accepted

Solution code:
import itertools
from bisect import bisect_right

num_lst = []
for i in range(10):
    for lst in itertools.product(["3", "5", "7"], repeat=i):
        if ("3" not in lst) or ("5" not in lst) or ("7" not in lst):
            continue
        num_lst.append(int("".join(lst)))
num_lst.sort()

n = int(input())
print(bisect_right(num_lst, n))