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:
from collections import Counter
import sys
sys.setrecursionlimit(10000)

s_n = input()
n = int(s_n)
ans = 0
add_list = ["3", "5", "7"]


def rec(now, i):
    # print(now, i)
    global ans
    coun = len(Counter(now))
    if coun > 2:
        # print("coun", coun)
        if int(now) <= n:
            # print("hoge")
            ans += 1
        else:
            return 0
    if i > -1:
        for j in range(3):
            rec(now + add_list[j], i-1)
    else:
        return 0


rec("", len(s_n)-1)
print(ans)

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 '3' in s and '5' in s and '7' in s and int(s) <= n:
            return 1
        return 0
    return dfs(i+1, s + '0') + dfs(i+1, s + '3') + dfs(i+1, s + '5') + dfs(i+1, s + '7')

print(dfs(0, ''))

Submission status: Accepted

Solution code:
import itertools
import collections

N = input()

if int(N) < 100:
    print(0)
    exit()

product_list = []
for i in range(3,len(N)+1):
    product_list += list(itertools.product('753', repeat=i))

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:
N = int(input())

def is_753(n):
    return '3' in list(str(n)) and '5' in list(str(n)) and '7' in list(str(n))

dict_753 = [3, 5, 7]

def generate753():
    list_753s = []
    for keta in range(3, 10):
        for n in range(3 ** keta):
            n_753 = 0
            for k in range(keta):
                n_753 = n_753 * 10 + dict_753[n % 3]
                n = int(n / 3)
            if is_753(n_753):
                list_753s.append(n_753)
    return list_753s

print(len([n for n in generate753() if n <= N]))

Submission status: Accepted

Solution code:
input = int(input())

total = 0
i = 357

while i <= input:
  
  target = list(map(int, str(i)))
  
  three = 0
  five = 0
  seven = 0
  error = 0
  
  for j, char in enumerate(target):
    
    char = int(char)
    
    if char != 3 and char != 5 and char != 7:
      keta = len(target) - j
      i += pow(10,keta-1)   
      error += 1

      break
    
    if char == 3:
      three += 1
    elif char == 5:
      five += 1
    elif char == 7:
      seven += 1
      
  if error > 0:
    continue
  
  if three > 0 and five > 0 and seven > 0:
    total += 1
  
  i += 1
    
print(total)

Submission status: Accepted

Solution code:
s = int(input())

import numpy as np
import itertools
candess = []
cnt = 0

for i in range(3, 10):
    candes = list((itertools.product([3,5,7], repeat=i)))
    for cande in candes:
        if (3 in cande) and (5 in cande) and (7 in cande) and \
        (int(''.join(map(str, cande)))) <= s:
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import product
def inpl(): return list(map(int, input().split()))
N = int(input())
ans = 0
for L in range(1, len(str(N))+1):
    for X in product("357", repeat=L):
        for s in "357":
            if not s in X:
                break
        else:
            ans += int("".join(X)) <= N

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
n = input()
x = int(n)
l = len(n)
if x < 357:
    print(0)
    sys.exit()
ans = 0
if l==3:
    if x>=753:
        print(6)
        sys.exit()
    elif 753>x>=735:
        print(5)
        sys.exit()
    elif 735>x>=573:
        print(4)
        sys.exit()
    elif 573>x>=537:
        print(3)
        sys.exit()
    elif 537>x>=375:
        print(2)
        sys.exit()
    elif 375>x>=357:
        print(1)
        sys.exit()
    else:
        print(0)
        sys.exit()

for i in range(3,l):
    ans += 3**i - 3*2**i + 3

if int(n[0]) > 7:
    ans += 3**l - 3*2**l + 3
    print(ans)
    sys.exit()

def check(arg):
    l = len(arg)
    c = 0
    for i,d in enumerate(arg):
        c+= d*10**(l-i-1)
    return c

def check2(x):
    if 3 in x and 5 in x and 7 in x:
        return True
    else:
        return False

for d in itertools.product([3,5,7], repeat=l):
    if check(d) <= x and check2(d):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

ans = 0

for i in range(3, 10):
    for j in range(3**(i)):
        s = 0
        cs = [0, 0, 0]
        for k in range(i):
            s += [3, 5, 7][(j // 3**(i - k - 1)) % 3] * 10**(i - k - 1)
            cs[(j // 3**(i - k - 1)) % 3] = 1
        if sum(cs) == 3 and s <= n:
            ans += 1

print(ans)

Submission status: Accepted

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

l = []
for i in range(3,10):
    ll = list(product(["3","5","7"],repeat = i))
    lll = list(map(list,ll))
    llll = list(map("".join, lll))
    lllll = list(map(int,llll))
    l.append(lllll)

x = []
for s in l:
    x.extend(s)
x.sort()
count = 0
for i in x:
    if i <= N and len(set(list(str(i)))&set(["3","5","7"]))==3:
        count += 1

print(count)

Submission status: Accepted

Solution code:
from itertools import product
ans=0
n=int(input())
for i in range(3,11):
    for m in product(["3","5","7"],repeat=i):
        if "3"not in m or "5"not in m or "7"not in m:
            continue
        if int("".join(m))<=n:
            ans+=1
        else:
            break
print(ans)

Submission status: Accepted

Solution code:
S = input()
D = len(S)
N = int(S)

if D <= 2:
    print(0)
    exit(0)

lst = [[], [], [], ["357", "375", "537", "573", "735", "753"]]
for d in range(4, D + 1):
    prev = lst[d - 1]
    lstd = []
    for si in prev:
        for i in range(len(si) + 1):
            lstd.append(si[:i] + '3' + si[i:])
            lstd.append(si[:i] + '5' + si[i:])
            lstd.append(si[:i] + '7' + si[i:])
    lst.append(list(set(lstd)))

count = 0
for i in range(3, D):
    count += len(lst[i])

lstd = [int(i) for i in list(set(lst[D]))]
lstd.sort()

import bisect
count += bisect.bisect(lstd, N)
print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from heapq import heappush, heapreplace
from itertools import count, product, combinations
from functools import partial, reduce
from math import floor, ceil, sqrt
from collections import defaultdict, deque

def Primes_fnct():
    def b_search(L,t):
        #増大列LについてL[:+1]の要素すべてがt以下であるような最大のi<len(L)を返す。
        search_range = [-1, len(L)]
        update_range = lambda mid: search_range.__setitem__(t<L[mid], mid)
        for _ in [0]*search_range[1].bit_length():
            update_range(sum(search_range)//2)
        return search_range[0]
    
    P = [2,]
    Pappend = P.append
    Q = deque([])
    Qappend = Q.append
    Qpopleft = Q.popleft
    hq = [] 
    integer = count(3,2)
    current_i = 1
    valid_range = 1
    def Primes(*, max_int=None):
        nonlocal valid_range, current_i
        if max_int is None:
            return P[:]

        if  max_int - current_i <= 1:
            return P[:b_search(P,max_int)+1]

        for i in integer:
            if i >= valid_range:
                if Q:
                    q = Qpopleft()
                    heappush(hq, (q**2,q))
                valid_range = Q[0]**2 if Q else i**2

            m,r = hq[0] if hq else (0,0)
            if i != m:
                Pappend(i)
                Qappend(i)

            while m == i:
                heapreplace(hq, (m+2*r, r))
                m,r = hq[0]

            current_i = i
            if max_int - current_i <=1:
                break 
        return P[:]
    return Primes

def factorization(m, Primes=None):
    F = defaultdict(int)
    if m < 2:
        return F

    while not m&1:
        F[2] += 1
        m >>= 1

    if Primes is None:
        Primes = Primes_fnct()

    Primes = deque(Primes(max_int=ceil(sqrt(m))+1))
    Primespopleft = Primes.popleft

    while m > 1 and Primes:
        p = Primespopleft()
        while not m%p:
            m //= p
            F[p] += 1

    if m > 1:
        F[m] += 1
    return F

def solve():
    N = int(input())
    res = 0
    flag = 1
    for d in range(3,10):
        if not flag:
            break
        for i in product('357', repeat=d):
            if set(i) == {'3','5','7'}:
                if int(''.join(i)) <= N:
                    res += 1
                else:
                    flag = 0
                    break
    return res



if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
n = int(input())
a = len(str(n))
ans = 0
x = 9
x2 = 4
for i in range(3, a):
    x *= 3
    x2 *= 2
    ans += x - x2 * 3 + 3
b = 0
l = ['3', '5', '7']
while(True):
    c = 3 ** (a - 1)
    s = ''
    bb = b
    for i in range(a):
        s += l[bb // c]
        bb = bb % c
        c = c // 3
    if int(s) > n or s.count('7') == a:
        break
    elif s.count('3') and s.count('5') and s.count('7'):
        ans += 1
    b += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
n = int(input())
count = 0
num = len(str(n))
for i in range(1,num+1):
    for balls in itertools.product([3,5,7],repeat=i):
        s = ""
        for c in balls:
            s += str(c)
        if int(s) <= n:
            lists = list(s) 
            if "7" in lists:
                if "5" in lists:
                    if "3" in lists:
                        count+=1
print(count)

Submission status: Accepted

Solution code:
n = int(input())
res = 0
ztfs = ["0", "3", "5", "7"]

for i1 in ztfs:
    for i2 in ztfs:
        for i3 in ztfs:
            for i4 in ztfs:
                for i5 in ztfs:
                    for i6 in ztfs:
                        for i7 in ztfs:
                            for i8 in ztfs:
                                for i9 in ztfs:
                                    num = i1+i2+i3+i4+i5+i6+i7+i8+i9
                                    if int(num) > n:
                                        print(res)
                                        exit()
                                    if "3" in num and "5" in num and "7" in num and (not "0" in str(int(num))):
                                        res += 1
print(res)

Submission status: Accepted

Solution code:
import math
def is_753(s) :
	
	if ("0" in s) :
		return False
	elif ("1" in s) :
		return False
	elif ("2" in s) :
		return False
	elif ("4" in s) :
		return False
	elif ("6" in s) :
		return False
	elif ("8" in s) :
		return False
	elif ("9" in s) :
		return False
	
	if ("7" in s and "5" in s and "3" in s) :
		return True
	
	return False

def hoge(s) :
	for i in range(len(s)) :
		if (s[i] != "3" and s[i] != "5" and s[i] != "7") :
			return int(math.pow(10, len(s) - (i+1)))

	return 0

def main() :
	N = int(input())
	count = 0
	index = 356
	
	if (N < 357) :
		print("0")
		return

	while index <= N :
		s = str(index)
		a = hoge(s)
		if (a != 0) :
			index += a
			continue		
		
		if (is_753(s)) :
			count += 1
		
		index += 1
	
	print(count)


main()

Submission status: Accepted

Solution code:
a3={'357','375','537','573','735','753'}
def make_a(a,n):
    new_a=set()
    for i in a:
        for j in range(n+1):
            new_a.add(i[:j]+'3'+i[j:])
            new_a.add(i[:j]+'5'+i[j:])
            new_a.add(i[:j]+'7'+i[j:])
    return new_a
a4=make_a(a3,3)
a5=make_a(a4,4)
a6=make_a(a5,5)
a7=make_a(a6,6)
a8=make_a(a7,7)
a9=make_a(a8,8)
a=list(map(int,a3))+list(map(int,a4))+list(map(int,a5))+list(map(int,a6))+list(map(int,a7))+list(map(int,a8))+list(map(int,a9))
n=int(input())
a.append(n)
a.sort()
ans=a.index(n)
if ans!=len(a)-1:
    if a[ans]==a[ans+1]:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import itertools
from collections import defaultdict

N=raw_input()
k=len(N)

if int(N)<357:
	print 0
	quit()

ans=0

for k in range(3,k+1):
	L=list(itertools.product( (3,5,7) , repeat=k))

	for t  in L:
		C=defaultdict(lambda: 0)
		v=0

		for idx, x in enumerate(t):
			v+=x*(10**idx)
			if x!=0:
				C[x]+=1
	
		if v<=int(N) and len(C)==3:
			ans+=1

print ans

Submission status: Accepted

Solution code:
def main():
    cand =[[0]]
    for i in range(1, l+1):
        cand.append([])
        for m in cand[i-1]:
            c = cand[i]
            c.append(m+3*(10**(i-1)))
            c.append(m+5*(10**(i-1)))
            c.append(m+7*(10**(i-1)))

    ret = 0
    for i in range(3, l+1):
        for j in cand[i]:
            set_ = set(str(j))
            if len(set_) < 3:
                continue
            if j <= n:
                ret += 1
    print(ret)

if __name__ == "__main__":
    s = input()
    n = int(s)
    l = len(s)
    main()

Submission status: Accepted

Solution code:
import itertools
n=int(input())
h = list(itertools.product(['7','5','3'],repeat=len(str(n))))
s=[0, 0, 0, 6, 36, 150, 540, 1806, 5796, 18150]
cnt=sum(s[:len(str(n))])
if n < 100:
    print(0)
else:
    for i in h:
        if any([j not in i for j in ['7','5','3']]):
            continue
        else:
            t=int(''.join(i))
            if n >= t:
                cnt+=1
    print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
LN = list(map(int, str(N)))
dig = len(LN)
Ans = 0

if N <= 99:print(0)
else:
    Ans += 0
    if N >= 1000:
        for i in range(3, dig):
            Ans += 3**i - 3 * 2**i + 3
    def base3(i, dig):
        t = i
        lt = []
        while t > 0:
            lt.append(t%3)
            t //= 3
        while len(lt) < dig:
            lt.append(0)
        out = 0
        for i in range(dig):
            out *= 10
            out += (3 if lt[i] == 0 else 5 if lt[i]==1 else 7)
        return out
    for i in range(3**dig + 1):
        num = base3(i, dig)
        if len(set(str(num))) == 3 and num <= N: Ans += 1
    print(Ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Dec  2 21:05:33 2018

@author: owner
"""

from math import log10

def cal(num,tup,k,max_,arr):
    r=0
    if k<0:
        if num <= max_ and arr[0]*arr[1]*arr[2]>0:
            return 1
        else:
            return 0
    for i,x in enumerate(tup):
        arr[i]+=1
        r+=cal(num+x*10**k,tup,k-1,max_,arr)
        arr[i]-=1
    return r

def fac(n):
    t=1
    for i in range(2,n+1):
        t*=i
    return t

N=int(input())
k=int(log10(N))

tup=(3,5,7)

ans=0
for i in range(2,k+1):
    ans+=cal(0,tup,i,N,[0,0,0])
print(ans)

Submission status: Accepted

Solution code:
import itertools

N=int(input())

nums=[7,5,3]
l=len(str(N))

def solve(n):
  res=0
  for SFT in itertools.product(nums, repeat=n):
    if len(set(SFT)) == 3:
      SFT=list(SFT)
      cnt=0
      for i in range(len(SFT)):
        cnt+=SFT[i]*(10**i)
      if cnt <= N:
        res+=1
  return res

if l < 3:
  print(0)
else:
  ans=0
  for i in range(3,l+1):
    ans+=solve(i)
  print(ans)

Submission status: Accepted

Solution code:
def check(i, num):

    global N, ans

    if i <= len(str(N)):
        if num <= N:
            list_n = list(map(int, list(str(num))))
            n3 = list_n.count(3)
            n5 = list_n.count(5)
            n7 = list_n.count(7)
            if n3 >= 1 and n5 >= 1 and n7 >= 1:
                ans += 1
                
        temp = 10 ** i   
        check(i + 1, num + 3 * temp)
        check(i + 1, num + 5 * temp)
        check(i + 1, num + 7 * temp)
    
N = int(input())
sn = str(N)

ans = 0

if len(sn) <= 2:
    print(0)
    exit()

check(0, 0)
    
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

base = ["3", "5", "7"]
nums = ["3", "5", "7"]
temp = []
x = 0

while 1:
    for num in nums[(3**x)-1:]:
        for b in base:
            temp.append(b + num)
    nums.extend(temp)
    
    x += 1
    if int(temp[-1]) > 10**9:
        break
    temp = []

target = []
for n in set(nums):
    if "7" in n and "5" in n and "3" in n:
        target.append(int(n))

count = 0
for n in target:
    if n <= N:
        count += 1

print(count)

Submission status: Accepted

Solution code:
N=int(input())

import itertools

ITER=[]
for i in range(3,10):
    ITER+=list(itertools.product([3,5,7],repeat=i))

def number(iter):
    
    s=""
    for l in iter:
        s+=str(l)
    return  int(s)
    
ANS=0
for iter in ITER:
    if 3 in iter and 5 in iter and 7 in iter:
        if number(iter)<=N:
            ANS+=1

print(ANS)