Problem:


Score : 500 points

Problem Statement

Find the number of integers between 1 and N (inclusive) that contains exactly K non-zero digits when written in base ten.

Constraints

1 \leq N < 10^{100}

1 \leq K \leq 3

Input

Input is given from Standard Input in the following format:

N
K

Output

Print the count.

Sample Input 1

100
1

Sample Output 1

19

The following 19 integers satisfy the condition:

1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90,100

Sample Input 2

25
2

Sample Output 2

14

The following 14 integers satisfy the condition:

11,12,13,14,15,16,17,18,19,21,22,23,24,25

Sample Input 3

314159
2

Sample Output 3

937

Sample Input 4

9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
3

Sample Output 4

117879300



Sample input:
100
1


Sample output:
19

Submission status: Runtime Error

Solution code:

N=int(input())
K=int(input())

keta1=len(str(N))
maxN=int(str(N)[0])
keta2=len(str(int(str(N)[1:])))
secN=int(str(int(str(N)[1:]))[0])
keta3=len(str(int(str(int(str(N)[1:]))[1:])))
thiN=int(str(int(str(int(str(N)[1:]))[1:]))[0])
only1=0
only2=0
if secN==0:
    only1=1
if str(int(str(int(str(N)[1:]))[0]))[0]==0:
    only2=1
import math

if keta1<K:
    print(0)
else:
    if K==1:
        print(maxN+9*(keta1-1))
    if K==2:
        if keta1-2!=0:
            if only1:
                print((maxN-1)*(keta1-1)*9+9**2*(keta1-2)*(keta1-1)//2)
            else:
                if keta2-1!=0:
                    print((maxN-1)*(keta1-1)*9+9**2*(keta1-2)*(keta1-1)//2+secN+(keta2-1)*9)
                else:
                    print((maxN-1)*(keta1-1)*9+9**2*(keta1-2)*(keta1-1)//2+secN)
        else:
            print((maxN-1)*(keta1-1)*9+secN)
    if K==3:
        if keta1-3!=0:
            if only1:
                print((maxN-1)*(keta1-1)*(keta1-2)//2*9**2+9**3*(keta1-3)*(keta1-2)*(keta1-1)//6)
            else:
                if keta2-2!=0:
                    print((maxN-1)*(keta1-1)*(keta1-2)//2*9**2+9**3*(keta1-3)*(keta1-2)*(keta1-1)//6+(secN-1)*9*(keta2-1)+9**2*(keta2-2)*(keta2-1)//2+thiN+(keta3-1)*9)
                else:
                    print((maxN-1)*(keta1-1)*(keta1-2)//2*9**2+9**3*(keta1-3)*(keta1-2)*(keta1-1)//6+(secN-1)*9*(keta2-1)+9**2*(keta2-2)*(keta2-1)//2+thiN)
        else:
            if only1:
                print((maxN-1)*(keta1-1)*9)
            else:
                print((maxN-1)*(keta1-1)*9+(secN-1)*9+thiN)

Submission status: Runtime Error

Solution code:
from math import factorial

factorial_L = [1] * 101
for i in range(2, 101):
    factorial_L[i] = factorial_L[i-1] * i

def permutations_count(n, r):
    return factorial_L[n] // factorial_L[n - r]


N_str = input()
N_int = int(N_str)
K = int(input())  # 1, 2, 3
ans = 0
keta = len(N_str)

S_keta = [[0] * (keta+1) for _ in range(K+1)]
for k in range(1, K+1):
    for i in range(1, keta+1):
        S_keta[k][i] = (permutations_count(i, k) // factorial_L[k]) * (9 ** (k))
        # if S_keta[k][i] == 0:
        #     S_keta[k][i] = 1



def solve(nketa, k):
    if k == 1 and nketa == 1:
        return int(N_str[-1])
    if k == 2 and nketa == 2:
        last_2 = int(N_str[-2])
        if last_2 == 0:
            return 0
        return int(last_2-1) * 9 + int(N_str[-1])
    
    if k == 0:
        return 1
    ret = 0
    ret += S_keta[k][nketa-1]
    # ret += ( int(N_str[keta-nketa])) * solve(nketa-1, k-1)
    if k-1 == 0:
        ret += int(N_str[keta-nketa])
    else:
        ret += (int(N_str[keta-nketa]) -1) * S_keta[k-1][nketa-1]
        ret += solve(nketa-1, k-1)
    return ret
print(solve(keta, K))

Submission status: Runtime Error

Solution code:
def nC2(n):
    return n*(n-1)/2

def nC3(n):
    return n*(n-1)*(n-2)/2/3

def K1(s):
    while s[0]=="0" and len(s)>0:
        s=s[1:]

    ll=len(s)

    if ll==1 or ll ==0:
        N=int(s[0])
    
    elif ll>1:
        N=int(s[0])+9*(ll-1)

    return N


def K2(s):
    while s[0]=="0" and len(s)>0:
        s=s[1:]
    
    ll=len(s)

    if ll==1 or ll ==0:
        N=0
    elif ll==2:
        N=(int(s[0])-1)*9+int(s[1])
    else:
        N=K1(s[1:])+(int(s[0])-1)*(ll-1)*9+9*9*nC2(ll-1)

    return N


def K3(s):
    ll=len(s)

    if ll ==1 or ll==2 or ll==0:
        N=0
    elif ll==3:
        N=(int(s[0])-1)*9*9+int(s[1])*int(s[2])
    else:
        N=K2(s[1:])+(int(s[0])-1)*nC2(ll-1)*9*9+nC3(ll-1)*9*9*9
    
    return N

N=input()
K=input()

if K=="1":
    ans=K1(N)
elif K=="2":
    ans=K2(N)
elif K=="3":
    ans=K3(N)


print(int(ans))

Submission status: Runtime Error

Solution code:
#!python3.4
# -*- coding: utf-8 -*-
# abc154/abc154_e
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2s()
    K = i2n()
    res = AEZ(N, K, 0)
    print(res)
    return

def AEZ(N, K, res):
    if K == 0:
        return 1
    N_len = len(N)
    under_d_sum = C(N_len - 1, K) * 9**K
    head = int(N[0])
    #print(N, K, res, under_d_sum, head)
    res = res + under_d_sum + (head-1) * AEZ('9'*(len(N)-1), K-1, res) + AEZ(N[1:], K-1, res)
    return res


def C(n,m):
    if n < m:
        return 0
    if n <= 0:
        return 0
    num = 1
    for i in range(m):
        num *= (n-i)
    if m == 3:
        m = 6
    return num // m

main()

Submission status: Runtime Error

Solution code:
def gcd(x, y):
    while(y): 
        x, y = y, x % y 
    return x
def NcR(n, r): 
    p = 1
    k = 1
    if (n - r < r): 
        r = n - r 
  
    if (r != 0):  
        while (r): 
            p *= n 
            k *= r 
            m = gcd(p, k) 
            p //= m 
            k //= m  
            n -= 1
            r -= 1
    else: 
        p = 1
    return p
def f1(n,a1):
    return (a1+9*(n-1))
def f2(n,a1,a2):
    s = 0
    if(n>=3):
        s = NcR(n-1,2) * 9**2
    if(n>=2):
        s+= (n-1) * (9) * (a1-1)
        s+= f1(n-1,a2)
    return s
def f3(n,a1,a2,a3):
    s = 0
    if(n>=4):
        s = NcR(n-1,3) * 9**3
    if(n>=3):
        s+= NcR(n-1,2) * (9**2) * (a1-1)
        s+= f2(n-1,a2,a3)
    return s
n = input()
k = input()
l = len(n)
if(k == '1'):
    print(f1(l,int(n[0])))
elif(k == '2'):
    print(f2(l,int(n[0]),int(n[1])))
else:
    print(f3(l,int(n[0]),int(n[1]), int(n[2])))

Submission status: Runtime Error

Solution code:
n = int(input())
k = int(input())
ans = 0
if k == 1:
    if n < 10:
        ans = n
    else:
        l = len(str(n))
        ans += 9 * (l - 1)
        ans += int(str(n)[0])
elif k == 2:
    if n < 11:
        ans = 0
    else:
        l = len(str(n))
        for i in range(2, l):
            ans += 9 * 9 * (i - 1)
        f = int(str(n)[0])
        ans += (f - 1) * 9 * (l - 1)
        for i in range(1, l):
            if int(str(n)[i]) != 0:
                f = int(str(n)[i])
                num = i
                break
        ans += f
        ans += 9 * (l - num - 1)
else:
    if n < 111:
        ans = 0
    else:
        l = len(str(n))
        for i in range(3, l):
            ans += 9 * 9 * 9 * (i - 1) * (i - 2) // 2
        f = int(str(n)[0])
        ans += (f - 1) * 9 * 9 * (l - 1) * (l - 2) // 2
        for i in range(1, l):
            if int(str(n)[i]) != 0:
                f = int(str(n)[i])
                num = i
                break
        ans += (f - 1) * (l - num - 1) * 9
        ans += 9 * 9 * (l - num - 1) * (l - num - 2) // 2
        for i in range(num + 1, l):
            if int(str(n)[i]) != 0:
                f = int(str(n)[i])
                num = i
                break
        ans += (l - num - 1) * 9
        ans += f
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

def ii(): return int(input())
def iis(): return input().split()
def imi(): return map(int,iis())
def iil(): return list(imi())


factmemo={0:1} #階乗
def fact(n):
    if n in factmemo:
        return factmemo[n]
    k = n*fact(n-1)
    factmemo[n]=k
    return k

def comb(a,b):
    if a-b < 0:
        return 0
    return fact(a)//(fact(a-b)*fact(b)) #組み合わせ

n = int(input())
k = int(input())
r = len(str(n))-1
st = str(n)
ans = 0
if k==1:
    ans += 9*r + int(st[0])
elif k==2:
    ans += 9**2 * comb(r, 2) + (int(st[0])-1) * 9**1 * comb(r, 1) + 9**1 * comb(r-1, 1) + int(st[1])
elif k==3:
    ans += comb(r, 3)*9**3\
           +comb(r, 2)*9**2*(int(st[0])-1)\
           +comb(r-1,2)*9**2\
           +comb(r-1, 1)*9**1*(int(st[1])-1)\
           +comb(r-2,1)*9\
           +int(st[2])




print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
k = int(input())
ans = 0
if k == 1:
    if n < 10:
        ans = n
    else:
        l = len(str(n))
        ans += 9 * (l - 1)
        ans += int(str(n)[0])
elif k == 2:
    if n < 11:
        ans = 0
    else:
        l = len(str(n))
        for i in range(2, l):
            ans += 9 * 9 * (i - 1)
        print(ans)
        f = int(str(n)[0])
        ans += (f - 1) * 9 * (l - 1)
        for i in range(1, l):
            if int(str(n)[i]) != 0:
                f = int(str(n)[i])
                num = i
                break
        ans += f
        ans += 9 * (l - num - 1)
else:
    if n < 111:
        ans = 0
    else:
        l = len(str(n))
        for i in range(3, l):
            ans += 9 * 9 * 9 * (i - 1) * (i - 2) // 2
        f = int(str(n)[0])
        ans += (f - 1) * 9 * 9 * (l - 1) * (l - 2) // 2
        for i in range(1, l):
            if int(str(n)[i]) != 0:
                f = int(str(n)[i])
                num = i
                break
        ans += (f - 1) * (l - num - 1) * 9
        ans += 9 * 9 * (l - num - 1) * (l - num - 2) // 2
        for i in range(num + 1, l):
            if int(str(n)[i]) != 0:
                f = int(str(n)[i])
                num = i
                break
        ans += (l - num - 1) * 9
        ans += f
print(ans)

Submission status: Runtime Error

Solution code:
def top(x):
  return int(x[0])
def digit(x):
  return len(x)

def nonzero_one(x):
  return (digit(x)-1)*9+top(x)

def nonzero_two(x):
  rt=0
  xtop=top(x)
  dig=digit(x)
  rt+=81*(dig-1)*(dig-2)//2
  rt+=(xtop-1)*9*(dig-1) 
  rt+=int(x[1])+9*(dig-2)
  return rt

def nonzero_three(x):
  rt=0
  xtop=top(x)
  dig=digit(x)
  rt+=729*(dig-1)*(dig-2)*(dig-3)//6
  rt+=(xtop-1)*81*(dig-1)*(dig-2)//2
  rt+=nonzero_two(x[1:])
  return rt

N=input()
K=int(input())
if K==1:
  print(nonzero_one(N))
elif K==2:
  print(nonzero_two(N))
else:
  print(nonzero_three(N))

Submission status: Runtime Error

Solution code:
import math
from scipy.misc import comb

N = input()
l = len(N)

number = int(input())
mam = comb(l, number, exact=True)
mam1 = comb(l-1, number, exact=True)*9**number
if number == 1:
  mam1 = comb(l-1, number, exact=True)*9**number
  mam1 += int(N[0])
  print(mam1)
if number == 2:
  mam1 = comb(l-1, number, exact=True)*9**number
  mam1 += (int(N[0])-1)*comb(l-1, number-1, exact=True)*9**(number-1)
  mam1 += int(N[1])+ (l-2)*9   
  print(mam1)
if number == 3:
  mam1 = comb(l-1, number, exact=True)*9**number
  mam1 += (int(N[0])-1)*comb(l-1, number-1, exact=True)*9**(number-1)
  mam1 += (int(N[1])-1)*comb(l-2, number-2, exact=True)*9**(number-2)
  mam1 += int(N[2])+ (l-3)*9
  print(mam1)

Submission status: Runtime Error

Solution code:
#!python3.4
# -*- coding: utf-8 -*-
# abc154/abc154_e
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2s()
    K = i2n()
    res = AEZ(N, K, 0)
    print(res)
    return

def AEZ(N, K, res):
    if K == 0:
        return 1
    N_len = len(N)
    under_d_sum = C(N_len - 1, K) * 9**K
    head = int(N[0])
    #print(N, K, res, under_d_sum, head)
    res = res + under_d_sum + (head-1) * AEZ('9'*(len(N)-1), K-1, res) + AEZ(N[1:], K-1, res)
    return res



def C(n,m):
    if n < m:
        return 0
    num = 1
    for i in range(m):
        num *= (n-i)
    if m == 3:
        m = 6
    return num // m

main()

Submission status: Runtime Error

Solution code:
import math
def comb(n,k):
  if n<=0 or k<0 or n<k:
    return 0
  return math.factorial(n)/(math.factorial(k) * math.factorial(n-k))


N=int(input())
K=int(input())
dig = []
n = math.floor(math.log10(N))+1
for i in range(n):
  dig.append(N // 10**(n-i-1))
N -= dig[i]

ans = 0
ans += (comb(n-1,K) * math.floor(9**K))

ans += (dig[0]-1)* ( (comb(n-2,K-1) * math.floor(9**(K-1))) + 9* (comb(n-2,K-2) * math.floor(9**(K-2))) )

ans += 1* ( (comb(n-2,K-1) * math.floor(9**(K-1))) + (dig[1])* (comb(n-2,K-2) * math.floor(9**(K-2))) )

ans += 1* ( (comb(n-3,K-2) * math.floor(9**(K-2))) + (dig[2])* (comb(n-3,K-3) * math.floor(9**(K-3))) )
print(int(ans))

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
s = readline().rstrip().decode('utf-8')
k = int(readline())
n = len(s)
"""
0の場所を固定してやる。
その時、9**(0以外が入る桁の数)が答え。
"""

from math import factorial

def permutations_count(n,r):
    """順列nPr"""
    return factorial(n) // factorial(n-r)

def combinations_count(n,r):
    """組み合わせnCr"""
    return factorial(n) // (factorial(n-r)*factorial(r))
if k == 1:
    i = 1
    ans = 0
    while True:
        if n == i:
            ans += int(s[0])
            break
        else:
            ans += 9
        i += 1
    print(ans)
    exit()

ans = 0
for i in range(1,n+1): #n+1桁
    if i < k:
        continue
    elif i == k:
        ans += 9**i
    else:
        ans += 9*(9**(k-1)*combinations_count(i-1,k-1)) #9は一番上の桁で、9通りが確定.kは1つ使っているのでk-1通りi桁からk-1個の並び

#現在、n桁(長さの桁)の9999...までの通りをカウントしてある。
#ここから、上位3桁に着目して、そこまでの分を引いてやる
if k == 2:
    point2 = int(s[:2]) #10~99までありえる
    delay = 0
    if point2 == 99:
        print(ans)
        exit()
    for i in range(point2,100):
        if not "0" in str(i):
            delay += 1
        else:
            delay += 9*(n-2)
    print(ans-delay)
else:
    point3 = int(s[:3])
    delay = 0
        if point3 == 999:
        print(ans)
        exit()
    for i in range(point3,1000):
        if not "0" in str(i):
            delay += 1
        else:
            if s[1:3] == "00":
                delay += 81*combinations_count(n-3,2)
            else:
                delay += 9*(n-3)
    print(ans-delay)

Submission status: Runtime Error

Solution code:
import math

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


def func(n, k):
    strn = str(n)
    lenn = len(strn)
    ret = cmb(lenn, k) * 9 ** k
    for x in [9 - int(c) for c in strn]:
        k -= 1
        y = cmb(lenn - 1, k)
        ret -= x * 9 ** k * y
        if k == 0:
            break

    return ret
N = int(input())
K = int(input())

print(func(N, K))

Submission status: Runtime Error

Solution code:
# import sys
# input = sys.stdin.readline

import itertools


def get_n(maxv, ln):
    n = 0

    if ln == 3:
        for i0 in range(1, 10):
            if i0 > maxv//100:
                continue
            for i1 in range(1, 10):
                for i2 in range(1, 10):
                    v = i0 * 100
                    v += i1 * 10
                    v += i2
                    if v <= maxv:
                        n += 1

    if ln == 2:
        for i0 in range(1, 10):
            for i1 in range(1, 10):
                v = i0 * 10
                v += i1
                if v <= maxv:
                    n += 1

    if ln == 1:
        for i0 in range(1, 10):
            v = i0
            if v <= maxv:
                n += 1
    return n


def main():
    N = input()
    K = int(input())

    d_n = len(N)
    c_list = [i for i in range(d_n)]

    combs = list(itertools.combinations(c_list, K))

    total = 0

    for comb in combs:

        if comb == (0, 1, 2):
            maxv = int(f'{N[int(comb[0])]}{N[int(comb[1])]}{N[int(comb[2])]}')
            n = get_n(maxv, 3)

        elif comb[0:2] == (0, 1):
            if len(comb) == 3:
                maxv = int(f'{N[int(comb[0])]}{N[int(comb[1])]}{"9"}')
            else:
                maxv = int(f'{N[int(comb[0])]}{N[int(comb[1])]}')
            n = get_n(maxv, len(comb))

        elif comb[0] == 0:
            maxv = int(f'{N[int(comb[0])]}{"9"*(len(comb)-1)}')
            n = get_n(maxv, len(comb))

        else:
            n = 9 ** len(comb)

        total += n

    print(total)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math
def comb(n,k):
if n<=0 or k<0 or n<k:
return 0
return math.factorial(n)/(math.factorial(k) * math.factorial(n-k))


N=int(input())
K=int(input())
dig = []
n = math.floor(math.log10())+1
for i in range(n):
dig.append(N // 10**(n-i-1))
N -= dig[i]

ans = 0
ans += (comb(n-1,K) * math.floor(9**K))

ans += (dig[0]-1)* ( (comb(n-2,K-1) * math.floor(9**(K-1))) + 9* (comb(n-2,K-2) * math.floor(9**(K-2))) )

ans += 1* ( (comb(n-2,K-1) * math.floor(9**(K-1))) + (dig[1])* (comb(n-2,K-2) * math.floor(9**(K-2))) )

ans += 1* ( (comb(n-3,K-2) * math.floor(9**(K-2))) + (dig[2])* (comb(n-3,K-3) * math.floor(9**(K-3))) )

Submission status: Runtime Error

Solution code:
N = input()
K = int(input())


M = len(N)

if K == 1:
    ans = (M - 1) * 9 + int(N[0])
    print(ans)

if K == 2:
    ans = int(N[1])
    ans += (M - 2) * 9
    ans += (int(N[0]) - 1) * (M - 1) * 9
    ans += (M - 1) * (M - 2) // 2 * 9 * 9
    print(ans)

if K == 3:
    ans = int(N[2])
    ans += (M - 3) * 9
    ans += (int(N[1]) - 1) * (M - 2) * 9
    ans += (M - 2) * (M - 3) // 2 * 9 * 9
    ans += (int(N[0]) - 1) * (M - 1) * (M - 2) // 2 * 9 * 9
    ans += (M - 1) * (M - 2) * (M - 3) // 6 * 9 * 9 * 9
    print(ans)

Submission status: Runtime Error

Solution code:
def f1(n,a1):
    return (a1+9*(n-1))
def f2(n,a1,a2):
    s = 0
    if(n>=3):
        s = NcR(n-1,2) * 9**2
    if(n>=2):
        s+= (n-1) * (9) * (a1-1)
        s+= f1(n-1,a2)
    return s
def f3(n,a1,a2,a3):
    s = 0
    if(n>=4):
        s = NcR(n-1,3) * 9**3
    if(n>=3):
        s+= NcR(n-1,2) * (9**2) * (a1-1)
        s+= f2(n-1,a2,a3)
    return s
n = input()
k = input()
l = len(n)
if(k == '1'):
    print(f1(l,int(n[0])))
elif(k == '2'):
    print(f2(l,int(n[0]),int(n[1])))
else:
    print(f3(l,int(n[0]),int(n[1]), int(n[2])))

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
k = int(input())
counter = 0
kotae = 0
num = 0
num2 = 0
s = str(num)
str_list = list(s)#文字列をリストに
int_list = [int(s) for s in str_list]

for i in range(n+1):
    num = i
    counter = 0
    if(len(s)<k):
        continue
    else:
        '''
        for j in range(len(s)):
            if(counter>k):
                break
            num2 = num // 10*10
            if(not num-num2==0):
                counter = counter + 1
            num = num//10
        '''
        if(np.count_nonzero(b) ==k):
            kotae = kotae + 1

print(kotae)

Submission status: Runtime Error

Solution code:
# import sys
# input = sys.stdin.readline

from itertools import combinations


def get_n(maxv, ln):
    n = 0

    if ln == 3:
        for i0 in range(1, 10):
            if i0 > maxv//100:
                continue
            for i1 in range(1, 10):
                for i2 in range(1, 10):
                    v = i0 * 100
                    v += i1 * 10
                    v += i2
                    if v <= maxv:
                        n += 1

    if ln == 2:
        for i0 in range(1, 10):
            for i1 in range(1, 10):
                v = i0 * 10
                v += i1
                if v <= maxv:
                    n += 1

    if ln == 1:
        for i0 in range(1, 10):
            v = i0
            if v <= maxv:
                n += 1
    return n


def main():
    N = input()
    K = int(input())

    d_n = len(N)
    c_list = [i for i in range(d_n)]

    combs = list(combinations(c_list, K))

    total = 0

    for comb in combs:

        if comb == (0, 1, 2):
            maxv = int(f'{N[int(comb[0])]}{N[int(comb[1])]}{N[int(comb[2])]}')
            n = get_n(maxv, 3)

        elif comb[0:2] == (0, 1):
            if len(comb) == 3:
                maxv = int(f'{N[int(comb[0])]}{N[int(comb[1])]}{"9"}')
            else:
                maxv = int(f'{N[int(comb[0])]}{N[int(comb[1])]}')
            n = get_n(maxv, len(comb))

        elif comb[0] == 0:
            maxv = int(f'{N[int(comb[0])]}{"9"*(len(comb)-1)}')
            n = get_n(maxv, len(comb))

        else:
            n = 9 ** len(comb)

        total += n

    print(total)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(raw_input())
k = int(raw_input())
count = 0

for i in range(1, n + 1):
    non_zero = 0
    for j in str(i):
        if not j == '0':
             non_zero += 1
    if non_zero == k:
        count += 1

print count

Submission status: Runtime Error

Solution code:
import math
from scipy.misc import comb

N = input()
l = len(N)

number = int(input())
mam = comb(l, number, exact=True)
mam1 = comb(l-1, number, exact=True)*9**number
if number == 1:
  mam1 = comb(l-1, number, exact=True)*9**number
  mam1 += int(N[0])
  print(mam1)
if number == 2:
  mam1 = comb(l-1, number, exact=True)*9**number
  mam1 += (int(N[0])-1)*comb(l-1, number-1, exact=True)*9**(number-1)
  mam1 += int(N[1])+ (l-2)*9   
  print(mam1)
if number == 3:
  mam1 = comb(l-1, number, exact=True)*9**number
  mam1 += (int(N[0])-1)*comb(l-1, number-1, exact=True)*9**(number-1)
  mam1 += int(N[1]-1)* (l-2)*9 +    int(N[2])+ (l-3)*9
  print(mam1)

Submission status: Runtime Error

Solution code:
N = input()
K = int(input())


M = len(N)

if K == 1:
    ans = (M - 1) * 9 + int(N[0])
    print(ans)

if K == 2:
    ans = int(N[1])
    ans += (int(N[1]) - 1) * (M - 2) * 9
    ans += (int(N[0]) - 1) * (M - 1) * 9
    ans += (M - 1) * (M - 2) // 2 * 9 * 9
    print(ans)

if K == 3:
    ans = int(N[2])
    ans += (M - 3) * 9
    ans += (int(N[1]) - 1) * (M - 2) * 9
    ans += (M - 2) * (M - 3) // 2 * 9 * 9
    ans += (int(N[0]) - 1) * (M - 1) * (M - 2) // 2 * 9 * 9
    ans += (M - 1) * (M - 2) * (M - 3) // 6 * 9 * 9 * 9
    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from sys import stdin
from copy import deepcopy
from functools import reduce
from fractions import gcd
import math
import itertools
from collections import Counter
from itertools import chain  ##list(chain.from_iterable(l)) ##flatten
from heapq import heappush, heappop

"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) ## 横一列
A = [int(input()) for _ in range(N)] ## 縦一列
lst = [list(map(int,input().split())) for i in range(M)] ## 二次元
"""

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result




def ABC154E(n, k):
  digit = len(str(n))
  if digit < k: ## 存在しないとき
    return 0
  elif k == 0: ## k=0のとき
    return 1
  elif n == int('9'*digit): ## 全ての桁が9のとき
    return combination(digit, k) * 9**k
  elif digit == 1: ## nが1桁のとき（この段階でk=1も決定される）
    return n
  else: ## 最高桁の値に応じて、次の小さい桁の数の漸化式に移行する
    bin_max = int(str(n)[0]) ## 最高桁の値
    var_0 = ABC154E(int('9'*(digit-1)), k) ## 最高桁が0の場合
    var_1 = ABC154E(int('9'*(digit-1)), k-1) * (bin_max - 1) ## 最高桁が1~(bin_max-1)の場合
    var_2 = ABC154E(int(str(n)[1:]), k-1) ## 最高桁が(bin_max)の場合
    return var_0 + var_1 + var_2


N = int(input())
K = int(input())

ans = ABC154E(N, K)

print(ans)

Submission status: Runtime Error

Solution code:
N=input()
K=int(input())
l=len(N)
dp=[[0]*(l+1) for i in range(K+1)]
dp[0][0]=1
x=0
for i,n in enumerate(N):
    n=int(n)
    dp[0][i+1]=1
    if n==0:
        for j in range(1,K+1):
            dp[j][i+1]=dp[j][i]+dp[j-1][i]*9
    else:
        for j in range(1,K+1):
        dp[j][i+1]=dp[j][i]+dp[j-1][i]*9 if i-j>-1 else 0 if i-j<-1 else n if i==0 else (dp[j-1][i]-1)*9+n
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
n=int(input())
k=int(input())
m=len(str(n))-1
b=0
c=0
for i in range(1,m):
    b+=i
for i in range(1,m-1):
    c+=i*(i+1)//2
if k==1:
    ans=9*m+int(str(n)[0])
elif k==2:
    for i in range(1,len(str(n))):
        if str(n)[i]!='0':
            X=i
            break
    ans=81*b+(int(str(n)[0])-1)*9*m+9*(m-X)+int(str(n)[X])
elif k==3:
    for i in range(1,len(str(n))):
        if str(n)[i]!='0':
            X=i
            break
    for i in range(X+1,len(str(n))):
        if str(n)[i]!='0':
            Y=i
            break
    ans=729*c+(int(str(n)[0])-1)*81*m*(m-1)//2
    ans+=(int(str(n)[X])-1)*(m-X)*9+(int(str(n)[Y])-1)*9*(m-Y)+int(str(n)[Y])
print(ans)

Submission status: Runtime Error

Solution code:

import math
from functools import reduce
import itertools

nstr = input()
n = int(nstr)
k = int(input())
l = len(nstr)
narr = [int(a) for a in nstr]

combnum = (lambda n, r: math.factorial(n) // (math.factorial(n - r) * math.factorial(r)))

result = 0
if l > k:
  result += combnum(l-1, k) * 9**k

result += combnum(l-1, k-1) * (narr[0]-1) * 9**(k-1)

if k == 1:
  result += 1
else:
  result += sum([reduce(lambda a, b: a*b, c) for c in itertools.combinations(narr[1:], k-1)])
print(result)

Submission status: Runtime Error

Solution code:
N=int(input())
K=int(input())

n=str(N)
n_digi=len(n)

import math

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)


if n_digi < K:
    print(0)

else:
    ans=0
    
    if n_digi>K:
        ans += permutations_count(n_digi-1,K)*9
    
    keta1=int(n[0])
    nokori=n[1:]
    
    if keta1 != 1 and K!=1:
        ans += (keta1-1)*ermutations_count(n_digi-2,K-1)*9
        
    elif keta1 != 1 and K==1:
        ans += (keta1-1)
        
    elif K==1 and int(nokori)==0:
        ans += 1
        
    else:
        noko_list = list(nokori)
        aa=1
        bb=sum(noko_list)
        for j in noko_list:
            aa *=j
             
        ans += aa-bb*(K-1)

Submission status: Runtime Error

Solution code:
def K1(n):
    ans = 0
    d = len(str(n))
    ans += int(str(n)[0])
    ans += 9 * (d-1)
    return ans


def K2(n):
    d = len(str(n))
    ans = 9**2*(d-2)*(d-1)//2
    ans += (int(str(n)[0]) - 1) * 9 * (d-1)
    ans += K1(int(str(n)[1:]))
    return ans


def K3(n):
    d = len(str(n))
    ans = 9**3*(d-2)*(d-3)//2
    ans += (int(str(n)[0]) - 1) * 9 * (d-1)
    ans += K2(int(str(n)[1:]))
    return ans


def main():
    N = int(input())
    K = int(input())

    if K == 1:
        print(K1(N))

    if K == 2:
        print(K2(N))

    if K == 3:
        print(K3(N))



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from scipy.special import comb

strn = input()
strk = input()
n = len(strn)
k = int(strk)
ue = int(strn[0])
sita = int(strn[-1])
print(ue,sita,n)

ans=0

if n-2>=k:
    ans= comb(n-2,k)*pow(9,k)
    print(ans)
if n-2 >= k-1 :
    ans=ans+comb(n-2,k-1)*pow(9,k-1)*sita
    print(ans)
if n-2>=k-2:
    ans = ans + sita*ue*comb(n-2,k-2)*pow(9,k-2)
    print(ans)
ans= int(ans)
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
K = int(input())
from math import log10
from operator import mul
from functools import reduce

def comb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


lg = int(log10(N))

def dp(n:int,k:int,K:int):
    lg = int(log10(N))
    if n > N:
        return 0
    if k > K:
        return 0
    if k == K:
        tmp = lg - int(log10(n))
        return tmp if n*10**tmp > N else tmp + 1
    sm = 0
    for i in range(1,10):
        sm += dp(n*10 + i,k + 1,K)
    return sm + dp(n*10,k,K)

memo = {}
def dp2(string:str,k:int):
    if (string,k) in memo:
        return memo[(string,k)]
    if k == 1:
        ans = 0
        for i in range(int( log10( N ) ) + 2):
            digit = 10**i
            for j in range(1,10):
                if j*digit <= N:
                    ans += 1
        memo[(string,k)] = ans
        return memo[(string,k)]

    if string[0] == "0":
        memo[(string,k)] =  dp2(string[1:],k)
        return memo[(string,k)]

    if len(string) > 3:
        ln = len(string)
        tmp = (comb(ln - 1,k)*9**k)*(string[0]) + dp2(string[1:],k)
        memo[(string,k)] = tmp
        return tmp
    memo[(string,k)] = dp(int(string),0,K)
    return memo[(string,k)]

def main():
    if K == 1:
        ans = 0
        for i in range(int( log10( N ) ) + 2):
            digit = 10**i
            for j in range(1,10):
                if j*digit <= N:
                    ans += 1
        print(ans)
        return
    if N < 10**10:
        ans = 0
        for i in range(1,10):
            ans += dp(i,1,K)
        print(ans)
    print(dp2(str(N),K))
    return

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
a = int(input())
b = int(input())

import math
q = len(str(a))-1

e = 9**b * math.factorial(q) // math.factorial(q-b)

for i in range(10**q, a+1):
  r = str(i)
  if len(r) - r.count("0") == b:
    e += 1
    
print(e)

Submission status: Runtime Error

Solution code:
from operator import mul
from functools import reduce

def com(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def run():
  N = int(input())
  K = int(input())
  Nnum = len(str(N))
  #1
  all1 = com(Nnum, K)*9**K
  #2
  all2 = (9-int(str(N)[0]))*com(Nnum-1, K-1)*9**(K-1)
  if K == 1:
    print(all1-all2)
  #3
  elif K == 2:
    all3 = 0
    for n in range(1, Nnum):
      N2 = int(str(N)[n])
      if N2 != 0:
        all3 += 9-N2
        break
      all3 += 9
    else:
      all3 = (Nnum-1)*9
    print(all1-all2-all3)
  #4
  else:
    all3 = 0
    count = 0
    for n in range(1, Nnum):
      N2 = int(str(N)[n])
      if N2 != 0:
        if count == 0:
          all3 += (9-N2)*com(Nnum-n-1, 1)*9
        elif count == 1:
          all3 += 9-N2
        count += 1
        if count == 2:
          break
      elif count == 0:
        all3 += 9*(Nnum-n-1)*9
      else:
        all3 += 9
    else:
      if count == 0:
        all3 = com(Nnum-1, 2)*9*9
      else:
        all3 = (Nnum-1)*9
    print(all1-all2-all3)
    
  

if __name__ == '__main__':
    run()

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
k = int(input())
counter = 0
kotae = 0
num = 0
num2 = 0
s = str(num)
char_list = list(s)#文字列をリストに
int_list = int(char_list)

for i in range(n+1):
    num = i
    counter = 0
    if(len(s)<k):
        continue
    else:
        '''
        for j in range(len(s)):
            if(counter>k):
                break
            num2 = num // 10*10
            if(not num-num2==0):
                counter = counter + 1
            num = num//10
        '''
        if(np.count_nonzero(b) ==k):
            kotae = kotae + 1

print(kotae)