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:
N = int(input())
ans = set(["3","5","7"])
list = ["3","5","7"]
x_list = ["3","5","7"]
cnt = 0
f = 0
i = 0

while f == 0:
    for j in range(3):
        num = x_list[i] + list[j]
        if int(num) > N:
            f = 1
            break
        x_list.append(num) 
    i += 1

for i in x_list:
    ans_list = [i for i in str(i)]
    s = set(ans_list)
    if s == ans:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
# Title: count Shichi-Go-San numbers under N
# Link: https://abc114.contest.atcoder.jp/tasks/abc114_c

import sys


sys.setrecursionlimit(10 ** 6)

read_single_int = lambda: int(sys.stdin.readline().strip())


def dfs(s: str, n: int, count: list):
    if int(s) > n:
        return
    if s.count('3') >= 1 and s.count('5') >= 1 and s.count('7') >= 1:
        count[0] += 1
    
    dfs(s+'3', n, count)
    dfs(s+'5', n, count)
    dfs(s+'7', n, count)


def solution(n: int):
    count = [0]
    dfs('0', n, count)
    return count[0]


def main():
    n = read_single_int()
    print(solution(n))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
divAble = [0 for i in range(len(str(n)))]
digit = len(str(n))
count = 0


def search(nowDigit, num, maxDigit, okList):
    if nowDigit < maxDigit:
        search(nowDigit + 1, num * 10 + 3, maxDigit, [1, okList[1], okList[2]])
        search(nowDigit + 1, num * 10 + 5, maxDigit, [okList[0], 1, okList[2]])
        search(nowDigit + 1, num * 10 + 7, maxDigit, [okList[0], okList[1], 1])
    else:
        if num <= n:
            # print("num:{}".format(num))
            global count
            if sum(okList) == 3:
                count += 1
for i in range(digit+1):
    search(0, 0, i, [0, 0, 0])
print(count)
"""
# 7, 5, 3
# nがk桁だとして
# 先頭が1,2,3,4,5,6-> 7は0～k-1つ、7,8,9なら0～kつ
if int(str(n)[0]) >= 7:
    divAble[0] += 1
elif n > 10:
        divAble[1] += 1

if int(str(n)[0]) >= 5:
    divAble[0] += 1
elif n > 10:
        divAble[1] += 1

if int(str(n)[0]) >= 3:
    divAble[0] += 1
elif n > 10:
        divAble[1] += 1

for i in range(1, len(divAble)):
    divAble[i] += divAble[i-1]

print(divAble)
if sum(divAble) == 0:
    print(0)
    exit()
count = 1
for i in range(len(divAble)):
    if divAble[i] > 0:
        count *= divAble[i]
print(count)
"""

Submission status: Accepted

Solution code:
def func(S, num):
    if len(S) == 10:
        return 0
    ret = 0
    if '3' in S and '5' in S and '7' in S and int(S) <= num:
        ret += 1
    ret += func(S + '3', num)
    ret += func(S + '5', num)
    ret += func(S + '7', num)
    return ret

print func('', input())

Submission status: Accepted

Solution code:
def func(S, num):
    ret = 0
    if '3' in S and '5' in S and '7' in S and int(S) <= num:
        ret += 1
    if len(S) == 10:
        return 0
    ret += func(S + '3', num)
    ret += func(S + '5', num)
    ret += func(S + '7', num)
    return ret

print func('', input())

Submission status: Accepted

Solution code:
lis = []
for i in range(3,10):
  l = []
  for _ in range(i):
   if l == []:
    l.append(["3","5","7"])
   else:
    c = l[-1]
    x1 = list(map((lambda x:x+"3"),c))
    x2 = list(map((lambda x:x+"5"),c))
    x3 = list(map((lambda x:x+"7"),c))
    l.append(x1+x2+x3)
  lis += l[-1]

l = [k for k in lis if k.count("3") and k.count("5") and k.count("7")]
l = list(map(int,l))

N = int(input())
if N in l:
 N += 1
l.append(N)
l.sort()
print(l.index(N))
quit()

Submission status: Accepted

Solution code:

ans = 0
def C4():
    N = int(input())
    def check(S):
        global ans
        s = 0
        f = 0
        t = 0
        #print(S)
        for j in list(S):
            if j == "7":
                s += 1
            if j == "5":
                f += 1
            if j == "3":
                t += 1
        if s != 0 and t != 0 and f != 0 and int(S) <= N:
            ans += 1

    def sarch(s):
        if int(s) <= N:
            check(s)
            sarch(s + '3')
            sarch(s + '5')
            sarch(s + '7')
    sarch("0")
    print(ans)
C4()

Submission status: Accepted

Solution code:
def C3():
    tmp = []
    import  copy

    for i in range(9):
        tmp.append([])
        tmp[i].append(3 * pow(10, i))
        tmp[i].append(5 * pow(10, i))
        tmp[i].append(7 * pow(10, i))

    tmp2 = [copy.copy(tmp[0])]
    for i in range(1, 9):
        tmp2.append([])
        for j in range(3):
            k = 0
            while True:
                if len(tmp2[i - 1]) <= k:
                    break
                tmp2[i].append(tmp[i][j] + tmp2[i - 1][k])
                k += 1
    N = int(input())
    tmp3 = []
    for i in range(2, 9):
        for j in range(len(tmp2[i])):
            tmp3.append(tmp2[i][j])
    ans = 0
    for i in tmp3:
        s = 0
        f = 0
        t = 0
        for j in list(str(i)):
            if j == "7":
                s += 1
            if j == "5":
                f += 1
            if j == "3":
                t += 1
        if s != 0 and t != 0 and f != 0 and int(i) <= N:
            ans += 1
    print(ans)

C3()

Submission status: Accepted

Solution code:
N = int(input())
def dfs(s=''):
    ans = 0
    if s!='' and int(s)>N:
        return 0
    elif '7' in s and '5' in s and '3' in s:
        ans += 1
    for c in ['3','5','7']:
        ans += dfs(s+c)
    return ans

ans = dfs()
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

def dfs(s):
  ret = 0
  if s == '':
    pass
  elif int(s) > n:
    return 0
  else:
    if '7' in s and '5' in s and '3' in s:
      ret = 1
  
  for c in ['7', '5', '3']:
    ret += dfs(s+c)
  
  return ret

print(dfs(''))

Submission status: Accepted

Solution code:
N = int(input())

def dfs(s): # 文字列 s で始まる七五三数の個数
	if int(s) > N:
		return 0
	ret = 1 if all(s.count(c) > 0 for c in '753') else 0 # s 自体が七五三数なら +1
	for c in '753':
		ret += dfs(s + c)
	return ret

print(dfs('0')) # 本当は dfs('') と書きたいが 4 行目でのエラーを防ぐため仕方なく

Submission status: Accepted

Solution code:
import itertools

N = int(input())
P = []

for i in range(len(str(N))): 
     P+= list(itertools.product(["7", "5", "3"], repeat = i + 1))

ans = 0
for i in P:
    if "7" not in i or "5" not in i or "3" not in i:
        continue
    a = int("".join(i))
    if a <= N:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = input()
def rec(list1,initial,time):
    empty = []
    for e in list1:
        for b in [0,1,2]:
            if b == 0:
                e_copy = e + "3"
                empty.append(e_copy)
            elif b == 1:
                e_copy = e + "5"
                empty.append(e_copy)
            elif b == 2:
                e_copy = e + "7"
                empty.append(e_copy)
    list1 = empty[:]
    # initial + 1 がn回目のループ
    if initial + 1 >= time :
        return list1
    else:
        return rec(list1,initial + 1, time)
l1 = [""]
result = [""]
for i in range(1,len(N)+1):
    result += rec(l1,0,i)
result = [int(e) for e in result if e.count("3")*e.count("5")*e.count("7") >= 1]
#result = list(set(result))
count = 0
for e in result:
    if int(N) < e:
        break
    count += 1
print(count)

Submission status: Accepted

Solution code:
n = int(raw_input().split()[0])

o1 = [3,5,7]
arr = [n]
ans = 0
def check(num):
    l = len(str(num))
    s = []
    for i in range(l):
        if str(num)[i] not in s:
            s.append(str(num)[i])
    if len(s) == 3:
        return True
    else:
        return False

for i in range(8):
    o2 = []
    for num in o1:
        new1 = num*10+3
        new2 = num*10+5
        new3 = num*10+7
        o2.append(new1)
        o2.append(new2)
        o2.append(new3)
        if check(new1):
            arr.append(new1)
            if n == new1:
                ans += 1
        if check(new2):
            arr.append(new2)
            if n == new2:
                ans += 1
        if check(new3):
            arr.append(new3)
            if n == new3:
                ans += 1
    o1 = o2
arr.sort()
print arr.index(n) + ans

Submission status: Accepted

Solution code:
def abc114_c():
    import numpy as np
    s = input()
    n = int(s)
    ans = 0

    nums = np.array([3, 5, 7])
    tmp = nums.copy()
    for i in range(1, len(s)):
        tmp = (tmp + [[3 * 10 ** i], [5 * 10 ** i], [7 * 10 ** i]]).flatten()
        nums = np.append(nums, tmp)

    for val in nums:
        str_val = str(val)
        if val <= n and "3" in str_val and "5" in str_val and "7" in str_val:
            ans += 1

    return ans


print(abc114_c())

Submission status: Accepted

Solution code:
s = input()
n = int(s)
dg = len(s)

all_list = []

for i in '753':
    for j in '753':
        for k in '753':
            all_list.append(''.join([i,j,k]))

for i in range(4,dg+1):
    add_list = []
    for c in '753':
        add_list += [''.join(c+e) for e in all_list]
    all_list += add_list

all_list = set(all_list)
res = sum([True for _ in all_list if set(list(_))=={'7','5','3'} and int(_) <= n])
print(res)

Submission status: Accepted

Solution code:
N = input()
def rec(list1,initial,time):
    empty = []
    for e in list1:
        for b in [0,1,2]:
            if b == 0:
                e_copy = e + "3"
                empty.append(e_copy)
            elif b == 1:
                e_copy = e + "5"
                empty.append(e_copy)
            elif b == 2:
                e_copy = e + "7"
                empty.append(e_copy)
    list1 = empty[:]
    # initial + 1 がn回目のループ
    if initial + 1 >= time :
        return list1
    else:
        return rec(list1,initial + 1, time)
l1 = [""]
result = rec(l1,0,3)
for i in range(len(N)-3):
    result += rec(result,0,1)
result = [int(e) for e in result if e.count("3")*e.count("5")*e.count("7") >= 1]
result = list(set(result))
result.sort()
count = 0
for e in result:
    if int(N) < e:
        break
    count += 1
print(count)

Submission status: Accepted

Solution code:
from math import log10

n = int(input())
m = int(log10(n)) + 1

ans = 0

def dfs(i, s):
    if i == m:
        if not '0' in str(int(s)) and all(a in s for a in '753') and int(s) <= n:
            return 1
        return 0
    res = 0
    for a in '0357':
        res += dfs(i+1, s + a)
    return res

print(dfs(0, ''))

Submission status: Accepted

Solution code:
N = int(input())


def to753(q):
    q, r = divmod(q, 4)
    r = 0 if r == 0 else 2 * r + 1  # 1->3, 2->5, 3->7
    if q == 0:
        return str(r)
    else:
        return to753(q) + str(r)


ans = 0
for qt in range(1, 4 ** 9):
    s = to753(qt)
    # print(qt, list(s))
    if '0' in s: continue
    if int(s) > N: break
    if all(c in s for c in '753'): ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = input()
def rec(list1,list2,initial,time):
    for e in list1:
        for b in [0,1,2,3]:
            if b == 0:
                e_copy = e
                list2.append(e_copy)
            elif b == 1:
                e_copy = e + "3"
                list2.append(e_copy)
            elif b == 2:
                e_copy = e + "5"
                list2.append(e_copy)
            elif b == 3:
                e_copy = e + "7"
                list2.append(e_copy)
    list1.clear()
    # initial + 1 がn回目のループ
    if initial + 1 >= time :
        return list2
    else:
        return rec(list2,list1,initial + 1, time)
l1 = [""]
l2 = []
result = rec(l1,l2,0,len(N))
result = [int(e) for e in result if e.count("3")*e.count("5")*e.count("7") >= 1]
result = list(set(result))
result.sort()
count = 0
for e in result:
    if int(N) < e:
        break
    count += 1
print(count)

Submission status: Accepted

Solution code:
n = int(input())
c = 0

def dfs(s):
    if int(s) > n:
        return
    # print(s)
    if '3' in s and '5' in s and '7' in s:
        global c
        c += 1
    
    dfs(s+'3')
    dfs(s+'5')
    dfs(s+'7')

dfs('0')
print(c)

Submission status: Accepted

Solution code:
from itertools import product
N = int(input())
res = 0
for length in range(1,11):
    for p in product('357',repeat=length):
        i = int(''.join(p))
        if i > N:
            print(res)
            exit()
        if all([c in p for c in '357']):
            res += 1

Submission status: Accepted

Solution code:
N = int(input())


def dfs(s):
    if int(s) > N:
        return 0
    ret = 1 if len(set(s)) == 4 else 0
    for i in ('3', '5', '7'):
        ret += dfs(s+i)
    return ret


print(dfs('0'))

Submission status: Accepted

Solution code:
list = ['3','5','7']
cnt = 0
ok = []

X = int(input())


for a in list:
    for b in list:
        for c in list:
            ok.append(a+b+c)
            for d in list:
                ok.append(a+b+c+d)
                for e in list:
                    ok.append(a+b+c+d+e)
                    for f in list:
                        ok.append(a+b+c+d+e+f)
                        for g in list:
                            ok.append(a+b+c+d+e+f+g)
                            for h in list:
                                ok.append(a+b+c+d+e+f+g+h)
                                for i in list:
                                    ok.append(a+b+c+d+e+f+g+h+i)

all = []
for i in ok:
    if i.count("3") >= 1 and i.count("5") >= 1 and i.count("7") >= 1:
        if int(i) <= X:
            cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import time
nlist = []

def findnums(lmax,lcur,num):

    if lmax < lcur :
        return
    elif lmax >= lcur :

        if lcur >= 3 :
            s = str(num)        
            if s.find('7') >= 0 and s.find('5') >= 0 and s.find('3') >= 0 :
                nlist.append(int(num))

        tmp = num + '3'
        findnums(lmax,lcur+1,tmp)
        tmp = num + '5'
        findnums(lmax,lcur+1,tmp)
        tmp = num + '7'
        findnums(lmax,lcur+1,tmp)

n = input()
keta = len(n)

t = time.time()
findnums(keta,0,'')
#print(time.time()- t)

t = time.time()
count = 0

for i in nlist:
    if int(n) >= i:
        count += 1

print(count)
#print(time.time()- t)

Submission status: Accepted

Solution code:
import queue

_in = input()
Nlen = len(_in)
N = int(_in)
glen = 1
ans = 0

findq = queue.Queue()
checkq = queue.Queue()

findq.put('3')
findq.put('5')
findq.put('7')

while glen <= Nlen and not findq.empty():
  head = findq.get()
  checkq.put(head)
  if len(head)+1 <= Nlen:
    glen = min(glen, len(head))
    findq.put(head+'3')
    findq.put(head+'5')
    findq.put(head+'7')

while not checkq.empty():
  head = checkq.get()
  if int(head) > N:
    continue
  if ''.join(sorted(set(head))) == '357':
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools as t;N=input();X=[]
for i in range(10):X+=list(t.product('357',repeat=i))
print(sum(len(set(i))>2and int(''.join(i))<=int(N)for i in X))

Submission status: Accepted

Solution code:
def make_candidate(N, seed, l):
    seed3 = seed+"3"
    seed5 = seed+"5"
    seed7 = seed+"7"

    if int(seed3) <= N:
        l.append(seed3)
        l = make_candidate(N, seed3, l)
    
    if int(seed5) <= N:
        l.append(seed5)
        l = make_candidate(N, seed5, l)
    
    if int(seed7) <= N:
        l.append(seed7)
        l = make_candidate(N, seed7, l)
    
    return l


N = int(input())

l = make_candidate(N, "0", [])

num = 0
for n in l:
    s = str(n)
    exist = s.count('3') * s.count('5') * s.count('7')

    if exist>0:
        num = num + 1

print(num)

Submission status: Accepted

Solution code:
N = int(input())
counter = 0
list = ['3','5','7']
ok = []
for a in list:
    for b in list:
        for c in list:
            ok.append(a+b+c)
            for d in list:
                ok.append(a+b+c+d)
                for e in list:
                    ok.append(a+b+c+d+e)
                    for f in list:
                        ok.append(a+b+c+d+e+f)
                        for g in list:
                            ok.append(a+b+c+d+e+f+g)
                            for h in list:
                                ok.append(a+b+c+d+e+f+g+h)
                                for i in list:
                                    ok.append(a+b+c+d+e+f+g+h+i)
                                    for j in list:
                                        ok.append(a+b+c+d+e+f+g+h+i+j)

sub = []
for _ in ok:
    x3 = _.count('3')
    x5 = _.count('5')
    x7 = _.count('7')
    if x3>0 and x5>0 and x7>0:
        sub.append(_)
fin = [int(_) for _ in sub]
fin.sort()
for _ in fin:
    if _ > N:
        print(fin.index(_))
        break

Submission status: Accepted

Solution code:
#!/usr/bin/env python

N = int(raw_input())
Array3 = [[] for i in range(9)]
Array5 = [[] for i in range(9)]
Array7 = [[] for i in range(9)]
Array53 = [[] for i in range(9)]
Array75 = [[] for i in range(9)]
Array73 = [[] for i in range(9)]
Array753 = [[] for i in range(9)]
Array3[0].append(3)
Array5[0].append(5)
Array7[0].append(7)
Arraytot = []

for i in range(8):
    Array753[i+1].extend(map(lambda x: x*10+7, Array753[i]))
    Array753[i+1].extend(map(lambda x: x*10+5, Array753[i]))
    Array753[i+1].extend(map(lambda x: x*10+3, Array753[i]))
    Array753[i+1].extend(map(lambda x: x*10+3, Array75[i]))
    Array753[i+1].extend(map(lambda x: x*10+5, Array73[i]))
    Array753[i+1].extend(map(lambda x: x*10+7, Array53[i]))
    Array75[i+1].extend(map(lambda x: x*10+5, Array75[i]))
    Array75[i+1].extend(map(lambda x: x*10+7, Array75[i]))
    Array75[i+1].extend(map(lambda x: x*10+7, Array5[i]))
    Array75[i+1].extend(map(lambda x: x*10+5, Array7[i]))
    Array73[i+1].extend(map(lambda x: x*10+3, Array73[i]))
    Array73[i+1].extend(map(lambda x: x*10+7, Array73[i]))
    Array73[i+1].extend(map(lambda x: x*10+7, Array3[i]))
    Array73[i+1].extend(map(lambda x: x*10+3, Array7[i]))
    Array53[i+1].extend(map(lambda x: x*10+3, Array53[i]))
    Array53[i+1].extend(map(lambda x: x*10+5, Array53[i]))
    Array53[i+1].extend(map(lambda x: x*10+5, Array3[i]))
    Array53[i+1].extend(map(lambda x: x*10+3, Array5[i]))
    Array3[i+1].extend(map(lambda x:x*10+3, Array3[i]))
    Array5[i+1].extend(map(lambda x:x*10+5, Array5[i]))
    Array7[i+1].extend(map(lambda x:x*10+7, Array7[i]))
    Arraytot.extend(Array753[i+1])

Arraytot.sort()
ans = 0
for i in Arraytot:
    if i <= N:
        ans+=1
    else:
        break
print ans

Submission status: Accepted

Solution code:
N = int(input())

def dfs(s): # 文字列 s で始まる七五三数の個数
    if int(s) > N:
        return 0
    ret = 1 if all(s.count(c) > 0 for c in '753') else 0 # s 自体が七五三数なら +1
    for c in '753':
        ret += dfs(s + c)
    return ret

print(dfs('0'))

Submission status: Accepted

Solution code:
from itertools import product
n = int(input())
a = ["3", "5", "7"]
b = []
for i in range(3, 10):
    for p in product(a, repeat=i):
        if all(p.count(q) for q in a):
            x = ""
            for j in range(len(p)):
                x += p[j]
            x = int(x)
            b.append(x)
ans = 0
for i in b:
    if i <= n:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
x = int(input())
s = 0
r = 0
def recur(i):
    global x
    global s
    global r
    if i < 0:
        if int(s) <= x:
            t = [False, False, False]
            while s > 0:
                c = s%10
                if c == 3:
                    t[0] = True
                if c == 5:
                    t[1] = True
                if c == 7:
                    t[2] = True
                s = s//10
            if t == [True, True, True]:
                r += 1
    else:
        b = s
        s = 10*b + 3
        recur(i-1)
        s = 10*b + 5
        recur(i-1)
        s = 10*b + 7
        recur(i-1)
        s = b

for w in range(12):
  if 10**w > x:
    break
  recur(w)
print(r)

Submission status: Accepted

Solution code:
N = int(input())


def make_357(now):
    if int(now) > N:
        return 0
    count = 0
    for c in '753':
        if now.count(c) > 0:
            count+=1
    count = count // 3
    for c in '753':
        count += make_357(now+c)
    
    return count

print(make_357('0'))