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())
lst = [[] for _ in range(10)]
lst[0] = [""]
for i in range(1, 10):
  for c in lst[i - 1]:
    for add in ("3", "5", "7"):
      lst[i].append(c + add)

def counter(l):
  ret = 0
  for s in l:
    if "3" in s and "5" in s and "7" in s and int(s) <= n:
      ret += 1
  return ret

ans = 0
for l in lst:
  ans += counter(l)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

def make753(X):
    add_ary = []
    for i in X:
        add_ary.append(int("3" + str(i)))
        add_ary.append(int("5" + str(i)))
        add_ary.append(int("7" + str(i)))
    return add_ary

L = []
L.append([3, 5, 7])
for i in range(10):
    L.append(make753(L[i]))

def flatten(nested_list):
    """2重のリストをフラットにする関数"""
    return [e for inner_list in nested_list for e in inner_list]

S = flatten(L)

true = []
for k in S:
    check = set(list(str(k)))
    if check == {'3', '5', '7'}:
        true.append(k)

true.sort()

z = 0
count = 0
while true[z] <= N:
    count += 1
    z += 1

print(count)

Submission status: Accepted

Solution code:
import numpy as np

def count(n,s):
    if s == 0:
        return 3**n - 3*(2**n) + 3
    elif s == 1:
        return 3**n - 2**(n+1) + 1
    elif s == 2:
        return 3**n - 2**n
    else:
        return 3**n

def num753(Nlist, appeared):
    n = len(Nlist)
    if n == 0:
        if appeared == 7:
            return 1
        else:
            return 0
    
    top = Nlist[-1]
    
    ap3 = appeared|1
    s3 = ap3 % 2 + (ap3 % 4)//2 + ap3 // 4
    ap5 = appeared|2
    s5 = ap5 % 2 + (ap5 % 4)//2 + ap5 // 4
    ap7 = appeared|4
    s7 = ap7 % 2 + (ap7 % 4)//2 + ap7 // 4

    if appeared == 0:
        ans = sum([count(i,0) for i in range(3,n)])
    else:
        ans = 0

    if top < 3:
        pass
    elif top == 3:
        ans = ans + num753(Nlist[:-1],ap3)
    elif top == 4:
        ans = ans + count(n-1,s3)
    elif top == 5:
        ans = ans + count(n-1,s3) + num753(Nlist[:-1],ap5)
    elif top == 6:
        ans = ans + count(n-1,s3) + count(n-1,s5)
    elif top == 7:
        ans = ans + count(n-1,s3) + count(n-1,s5) + num753(Nlist[:-1],ap7)
    else: # top == 8,9
        ans = ans + count(n-1,s3) + count(n-1,s5) + count(n-1,s7)
    
    return ans

N = int(input())
Nlist=[]
while N > 0:
    Nlist.append(N % 10)
    N = N // 10
Nlist = np.array(Nlist,dtype=np.int)

print(num753(Nlist,0))

Submission status: Accepted

Solution code:
from itertools import product
n = int(input())
if n <= 356:
	print(0)
else:
	ans = 0
	shi_list = ["3", "5", "7"]
	shi_set = {"3", "5", "7"}
	for i in range(3, len(str(n))+1):
		for num in product(shi_list, repeat=i):
			x = int("".join(num))
			if x <= n and set(list(str(x))) & shi_set == shi_set:
				ans += 1
	print(ans)

Submission status: Accepted

Solution code:
import math
import numpy as np
import itertools
import sys
N = int(input())

#Nをリストにした（int）
Nl = list(map(int, list(str(N))))

#Nの桁数
size = int(math.log10(N) + 1)

#答え
ans = 0

#3〜m-1桁まで
size_l = list(np.arange(3, size))
for m in size_l:
	c = 3**m - 3 * 2**m + 3 * 1**m
	ans += c
#ここまででm-1桁目まで数え上げてる

A = ['3','5','7']
l = list(itertools.product(A, repeat=size))
def tyo(x):
	if '3' in x and '5' in x and '7' in x:
		return x
	else:
		return ''
def aaa(x):
	ans = ''.join(x)
	if not ans == '':
		return ans
l = list(map(tyo, l))
l = list(map(aaa, l))
l = [item for item in l if item]
l = list(map(int, l))
l.sort()
l = [item for item in l if item <= N]
ans += len(l)
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
N = int( input())
ans = 0
for i in range(3,10):
    for x in product("357", repeat = i):
        z = ""
        V = [0]*10
        for l in x:
            z += l
            V[ int( l)] = 1
        if int(z) <= N and sum(V) == 3:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
def count(s):
    if len(s) == len(str(n)):
        if ('3' in s) and ('5' in s) and ('7' in s) and (int(s) <= n) and not ('0' in str(int(s))):
            #print(s)
            return 1
        else:
            return 0
    ret = 0
    for i in "0357":
        ret += count(s+i)
    return ret

print(count(""))

Submission status: Accepted

Solution code:
N = int(input())

i = 357
count = 0
if 357 <= N:
    while(1):
        flag = 0
        flag7 = 0
        flag5 = 0
        flag3 = 0
        for j,s in enumerate(str(i)):
            if s != "7" and s != "5" and s != "3":
                flag = 1
                i += 10 ** (len(str(i)) - j - 1)
                break
            if s == "7":
                flag7 = 1
            elif s == "5":
                flag5 = 1
            elif s == "3":
                flag3 = 1
        if flag == 0 and flag7 == 1 and flag5 == 1 and flag3 == 1:
            count += 1
        if flag == 0:
            i += 1
        if N < i:
            break

print(count)

Submission status: Accepted

Solution code:

import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

g_comb_table ={}
def Comb(n, k):
    global g_comb_table
    if (n, k) in g_comb_table:
        return g_comb_table[(n, k)]
    if n == k or k == 0:
        g_comb_table[(n, k)] = 1
        return 1L
    elif k == 1:
        g_comb_table[(n, k)] = n
        return n
    g_comb_table[(n, k)] = Comb(n-1, k-1) + Comb(n-1, k)
    return g_comb_table[(n, k)]



def count(dig, msd, msd_bound):
    if msd < msd_bound:
        return int(3 ** max(0, (dig - 3))) * max(0, (dig - 1)) * max(0, (dig - 2)) * max(0, (dig - 3))
    else:
        return int(3 ** max(0, (dig - 3))) * max(0, (dig - 2)) * max(0,(dig - 1)) * max(0, (dig - 2))


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [int(input_raw[0])]
    S = "0753"
    already = set([])
    count = 0
    for s1 in S:
        for s2 in S:
            for s3 in S:
                for s4 in S:
                    for s5 in S:
                        for s6 in S:
                            for s7 in S:
                                for s8 in S:
                                    for s9 in S:
                                        s = s1+s2+s3+s4+s5+s6+s7+s8+s9
                                        s = s.strip()
                                        if (len(s) == 0): continue;
                                        i = int(s1+s2+s3+s4+s5+s6+s7+s8+s9)
                                        s = str(i)
                                        if i <= N and i not in already:
                                            if ("7" in s) and ("3" in s) and ("5" in s) and ("0" not in s):
                                                count += 1
                                                already.add(i)


##    dig = int(math.log(N, 10)) + (0 if N % 10 == 0 else 1)
##    msd = N / (10**(dig - 1))
##    if msd < 5:
##        las = 1
##    elif msd < 7:
##        las = 2
##    else:
##        las = 3
##    C1 = Comb(dig, 3)
##    top7 = count(dig, msd, 7)
##    top5 = count(dig, msd, 5)
##    top3 = count(dig, msd, 3)
    print  count

    #for i in range(dig):


if __name__ == '__main__':
    main()