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: Accepted

Solution code:
n=input()
k=int(input())


if int(n)<1000:
    c=0
    for i in range(1,int(n)+1):
       if len(str(i))-str(i).count("0")==k:
           c+=1
else:
    n_l=len(n)
    c=0
    if k==1:
        c=int(n[0])+9*(n_l-1)
    elif k==2:
        for i in range(2,n_l):
            c+=9*9*(i-1)
        c+=(int(n[0])-1)*9*(n_l-1)
        
        for i in range(1,n_l):
            if int(n[i])>0:
                c+=int(n[i])+(n_l-i-1)*9
                break

    else:
        for i in range(3,n_l):
            c+=9**3*((i-1)*(i-2)/2)
                    
        c+=(int(n[0])-1)*9*9*((n_l-1)*(n_l-2)/2)
        
        flag_i=False
        flag_j=False
        for i in range(1,n_l):
            if int(n[i])>0:
                flag_i=True
                for j in range(i+1,n_l):
                    if int(n[j])>0:
                        flag_j=True
                        break
            if flag_i:
                break
        if flag_i:
            c+=(int(n[i])-1)*9*(n_l-i-1)
            c+=9*9*((n_l-i-1)*(n_l-i-2)*0.5)
            if flag_j:
                c+=(int(n[j]))+9*(n_l-j-1)
                
print(int(c))

Submission status: Accepted

Solution code:
MOD = 1000000007
INF = float("inf")

n = int(input())
k = int(input())

len_n = len(str(n))
# print(len_n)
if len_n < k:
    print(0)
    exit()

base = [[0]*4 for _ in range(200)]

for i in range(200):
    base[i][0] = 1
for i in range(1, 200):
    base[i][1] = 9 * i
for i in range(2, 200):
    base[i][2] = 9 * 9 * i*(i-1)//2
for i in range(3, 200):
    base[i][3] = 9 * 9 * 9 * i * (i - 1) * (i-2) // 6

ans = 0
len_n = len(str(n))
n_str = str(n)

for i in range(len(n_str)):
    # print(len_n)
    if int(n_str[i]) > 0:
        ans += (int(n_str[i])-1)*base[len_n-1][k-1] + base[len_n-1][k]
        # print(ans)
        if k == 1:
            ans += 1
        k -= 1
    len_n -= 1
    if k == 0:
        break

print(ans)

Submission status: Accepted

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

N = readline().strip()
K = int(readline())

MM = [9, 81, 9 ** 3]

def comb(n, k):
    a = 1
    for i in range(k):
        a *= n - i
    
    for i in range(k):
        a = a // (i + 1)
    
    return a

def xxx(N, K):
    L = len(N)
    if L <= K - 1:
        return 0
    
    if K == 0:
        return 1
    
    a = comb(L - 1, K) * MM[K - 1]

    b = int(N[0]) - 1
    a += b * comb(L - 1, K - 1) * MM[K - 2] if K >= 2 else b
    
    _i = L
    for i in range(1, L):
        if N[i] != '0':
            _i = i
            break

    if _i < L:
        a += xxx(N[_i:], K - 1)
    elif K == 1:
        a += 1
    return a

print(xxx(N, K))

Submission status: Accepted

Solution code:
def almost0(m,K):
    M=str(m)
    s=len(M)
    if s<K:
        return 0
    elif m==0:
        return 0
    elif K==0:
        return 0
    elif K==1:
        return int(M[0])+almost0((10**(len(M)-1))-1,K)
    elif K==2:
        return (int(M[0])-1)*9*(len(M)-1)+almost0(m%(10**(len(M)-1)),K-1)+almost0((10**(len(M)-1))-1,K)
    else:
        return  (int(M[0])-1)*81*(s-1)*(s-2)//2+almost0(m%(10**(s-1)),K-1)+almost0((10**(s-1))-1,K)

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

print(almost0(N,K))

Submission status: Accepted

Solution code:
from functools import lru_cache
N = input()
K = int(input())

## lru_cacheを使ってメモ化
@lru_cache(maxsize=None)
def rec(k,tight,sum_val):
    # 最後まで探索した時、問題条件に応じて1 or 0を返す
    if k == len(N):
        if sum_val == K and sum_val != 0:
            return 1
        else:
            return 0

    # 現在の桁がtightであるか否かで終了する条件を変更する
    x = int(N[k])
    if tight:
        r = x
    else:
        r = 9
    res = 0
    for i in range(r + 1):
        if i == 0:
            res += rec(k + 1 ,tight and i == r, sum_val)
        else:
            res += rec(k + 1, tight and i == r, sum_val + 1)

    return res



print(rec(0 , True , 0))

Submission status: Accepted

Solution code:
n = int(input())
k = int(input())

def c(n, k):
    if n < k:
        return 0
    else:
        x = 1
        for i in range(k):
            x *= (n - i)
            x //= (i + 1)
        return x

ans = 0
for i in range(k):
    temp1 = len(str(n)) - 1
    temp2 = n // (10 ** temp1)
    check = k - i
    if check == 1:
        ans += temp2 + temp1 * 9
    else:
        ans += c(temp1, check) * (9 ** check) + (temp2 - 1) * c(temp1, check - 1) * (9 ** (check - 1))
    n %= 10 ** temp1
print(ans)

Submission status: Accepted

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

DP = [[[1,0,0,0,],[0,0,0,0]] for i in range(len(N)+1)]
for i in range(len(N)):
    if N[-1-i] == '0':
        for k in range(K):
            DP[i+1][0][k+1] = DP[i][0][k+1]
            DP[i+1][1][k+1] = DP[i][1][k+1]
    else:
        for k in range(K):
            DP[i+1][0][k+1] = DP[i][0][k+1]+DP[i][1][k+1]
    for j in range(1,10):
        for k in range(K):
            if j > int(N[-1-i]):
                DP[i+1][1][k+1] += DP[i][1][k] + DP[i][0][k]
            elif j < int(N[-1-i]):
                DP[i+1][0][k+1] += DP[i][1][k] + DP[i][0][k]
            elif j == int(N[-1-i]):
                DP[i+1][0][k+1] += DP[i][0][k]
                DP[i+1][1][k+1] += DP[i][1][k]
"""
for i in DP:
    for j in i:
        print(j)
    print()
"""
print(DP[-1][0][K])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

def solve_1(N):
    N_str = str(N)
    ans = 0
    for i, ch in enumerate(N_str):
        if i == 0:
            ans += int(ch)
        else:
            ans += 9
    return ans

def solve_2(N):
    N_str = str(N)

    # N = 72543

    # 6XXXX
    ans = (int(N_str[0]) - 1) * 9 * (len(N_str) - 1)

    # 7XXXX
    flag = False
    for ch in N_str[1:]:
        if flag:
            ans += 9
        else:
            ans += int(ch)
            if ch != '0':
                flag = True

    # XXXX
    for i in range(1, len(N_str) - 1):
        ans += 81 * i

    return ans

def solve_slow_2(n):
    ans = 0
    for i in range(1, n + 1):
        i_str = str(i)
        cnt = 0
        for ch in i_str:
            cnt += ch != '0'
        ans += cnt == 2
    return ans

# for n in range(1, 10000):
#     mine = solve_2(n)
#     gt = solve_slow_2(n)
#     if mine != gt:
#         print("error! n, mine, gt = ", n, mine, gt)
#         sys.exit(0)
#     else:
#         print(n, "ok")


def solve_3(N):
    N_str = str(N)
    size = len(N_str)

    # N = 72543

    # 6XXXX
    ans = (int(N_str[0]) - 1) * (((size - 1) * (size - 2)) // 2) * 81

    # 7XXXX
    # -> XXXX
    if size > 1:
        ans += solve_2(int(N_str[1:]))

    # XXXX
    for size in range(1, len(N_str)):
        ans += 9 * 9 * 9 * (size - 1) * (size - 2) // 2

    return ans

def solve_slow_3(n):
    ans = 0
    for i in range(1, n + 1):
        i_str = str(i)
        cnt = 0
        for ch in i_str:
            cnt += ch != '0'
        ans += cnt == 3
    return ans

# for n in range(1, 10000):
#     mine = solve_3(n)
#     gt = solve_slow_3(n)
#     if mine != gt:
#         print("error! n, mine, gt = ", n, mine, gt)
#         sys.exit(0)
#     else:
#         print(n, "ok")
        

def solve(N, K):
    if K == 1:
        return solve_1(N)
    elif K == 2:
        return solve_2(N)
    else:
        return solve_3(N)


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

print(solve(N, K))

Submission status: Accepted

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

len_n = len(n)

dp = []
for _ in range(len_n + 1):
    dp.append([[0] * 4 for __ in range(2)])

# dp = [ [[0] * K] for __ in range(2)  for _ in range(len_n + 1)]
dp[0][1][0] = 1

for i in range(1, len_n+1):
    now = int(n[i-1])

    dp[i][0][0] = 1
    for j in range(1,4):
        dp[i][0][j] = dp[i-1][0][j] + dp[i-1][0][j-1] * 9
        if(now == 0):
            dp[i][1][j] = dp[i-1][1][j]
        else:
            dp[i][0][j] += dp[i-1][1][j]
            dp[i][0][j] += dp[i-1][1][j-1] * (now-1)
            dp[i][1][j] = dp[i-1][1][j-1]

print(dp[-1][0][K] + dp[-1][1][K])

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def f(k,p):
    if p<k:
        ret = 0
    if k==0:
        ret = 1
    elif k==1:
        ret = p*9
    elif k==2:
        ret = 9*9*p*(p-1)//2
    else:
        ret = 9*9*9*p*(p-1)*(p-2)//6
    #ddprint("f k {} p {} ret {}".format(k,p,ret))
    return ret

def g(k,p,n):
    #ddprint("g k {} p {} n {} called".format(k,p,n))
    if p==0 or p<k:
        return 0
    if k==0:
        ret = 1
    elif p==1:
        ret = n
    elif n<10**(p-1):
        ret = g(k,p-1,n)
    else:
        m = n//(10**(p-1))
        ret = g(k-1,p-1,n-m*(10**(p-1))) + (m-1)*f(k-1,p-1) + f(k,p-1)
    #ddprint("g k {} p {} n {} ret {}".format(k,p,n,ret))
    return ret

n = inn()
k = inn()
print(g(k,100,n))

Submission status: Accepted

Solution code:
N=input()
K=int(input())
m=len(N)
a=0
if K==3:
    for i in range(1,m-2):
        a+=i*(i+1)
    a//=2
    a*=729
    for i in range(1,10):
        for j in range(1,10):
            for k in range(1,10):
                for b in range(m-2):
                    for c in range(m-2-b):
                        if N>=str(i)+"0"*b+str(j)+"0"*c+str(k)+"0"*(m-3-b-c):
                            a+=1
elif K==1:
    if int(N)<10:
        a=int(N)
    else:
        a=9
        for i in range(2,m):
            a+=9
        for i in range(1,10):
            if N>=str(i)+"0"*(m-1):
                a+=1
else:
    for i in range(1,m-1):
        a+=i
    a*=81
    for i in range(1,10):
        for j in range(1,10):
            for k in range(m-1):
                if N>=str(i)+"0"*k+str(j)+"0"*(m-2-k):
                    a+=1
print(a)

Submission status: Accepted

Solution code:
import math
n=input()
k=int(input())
t=0
def com(a,b):
    if b>a:
        return 0
    else:
        return math.factorial(a)//(math.factorial(b)*math.factorial(a-b))
def su(n,k,i,s):
    if s==0:
        return 1
    if len(n)-i<s:
        return 0
    if n[i]=="0":
        return su(n,k,i+1,s)
    else:
        return (9**s)*(com(len(n)-i-1,s))+(int(n[i])-1)*(9**(s-1))*(com(len(n)-i-1,s-1))+su(n,k,i+1,s-1)
print(su(n,k,0,k))

Submission status: Accepted

Solution code:
import sys

def comb(n, k):
    if k == 0:
        return 0
    if n < k:
        return 0
    res=1
    for i in range(n - k + 1, n + 1):
        res *= i
    for i in range(1,k + 1):
        res //= i
    return res

n=input()
k = int(input())
l = len(n)

top = int(n[0])

if l == 1:
    if k >= 2:
        print(0)
        sys.exit()
    print(top)
    sys.exit()

if k == 1:
    z = 9
elif k == 2:
    z = 81
else:
    z = 729

ans = comb(l - 1, k) * z
ans += comb(l - 1, k - 1) * (top - 1) * (z // 9)

if k == 1:
    ans+=top
elif k == 2:
    for i in range(1, l):
        if i==1 or int(n[1:i]) == 0:
            ans += int(n[i])
        else:
            ans += 9
elif k == 3:
    for i in range(1, l):
        for j in range(i + 1, l):
            flag1 = i == 1 or int(n[1:i]) == 0
            flag2 = j == i + 1 or int(n[i + 1 :j]) == 0
            if not(flag1) and not(flag2):
                ans += 81
            elif flag1 and not (flag2):
                ans += 9 * int(n[i])
            elif not (flag1) and flag2:
                ans += 81
            else:
                if int(n[i]) == 0:
                    continue
                ans += 9 * (int(n[i]) - 1) + int(n[j])

print(ans)

Submission status: Accepted

Solution code:
import math

def combinations_count(n, r):
  if n>=r:
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
  else:
    return 0

str_n=input()
k=int(input())
cnt=0
dig = len(str_n)

#最上位桁が最大以外の場合　かつ　0でない場合
cnt += (int(str_n[0])-1)*combinations_count(dig-1,k-1)*9**(k-1)
#最上位桁が0の場合
if dig-1>=k:
  cnt += combinations_count(dig-1,k)*9**k

#最上位桁が最大の場合
if k==1:
  cnt+=1
else:
  ##第２非ゼロ桁の探索
  for i in range(dig-1):
    if str_n[i+1] != '0':
      dig2 = i+1
      break
  else:
    print(cnt)
    exit()
  ##第２非ゼロ桁が最大以外の場合　かつ　0でない場合
  cnt += (int(str_n[dig2])-1)*combinations_count(dig-1-dig2,k-2)*9**(k-2)
  ##第２非ゼロ桁が0の場合
  if dig-1-dig2>=k-1:
    cnt += combinations_count(dig-1-dig2,k-1)*9**(k-1)
  ##第２非ゼロ桁が最大の場合
  if k==2:
    cnt+=1
  else:
    ##第３非ゼロ桁の探索
    for i in range(dig-1-dig2):
      if str_n[i+1+dig2] != '0':
        dig3 = i+1+dig2
        break
    else:
      print(cnt)
      exit()
    ##第３非ゼロ桁が0でない場合
    cnt += int(str_n[dig3])
    ##第３非ゼロ桁が0の場合
    cnt += combinations_count(dig-1-dig3,k-2)*9**(k-2)
print(cnt)

Submission status: Accepted

Solution code:
#import re
import sys
input = sys.stdin.readline
#import heapq
#import bisect
#from collections import deque
#import math

def main():
    n = input().strip()
    k = int(input())
    if k == 1:
        ans = k1(n)
    elif k == 2:
        ans = k2(n)
    elif k == 3:
        ans = k3(n)
    
    print(int(ans))


def k1(n):
    ans = 0
    return 9*(len(n)-1)+int(n[0])

def k2(n):
    ans = 0
    if len(n) == 1:
        ans = 0
    elif len(n) >= 2:
        ans += k1(str(int(n[1:])))
        ans += (int(n[0])-1)*9*(len(n)-1)
        ans += 9*9*(len(n)-1)*(len(n)-2)/2
    return ans

def k3(n):
    ans = 0
    if len(n) <= 2:
        ans = 0
    elif len(n) >= 3:
        ans += k2(str(int(n[1:])))
        ans += (int(n[0])-1)*9*9*(len(n)-1)*(len(n)-2)/2
        ans += (len(n)-1)*(len(n)-2)*(len(n)-3)/6*9**3
    return ans

    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = input()
K = int(input())
def Anger(n, k):
  d = int(n[0])
  if len(n) < k:
    return 0
  else:
    if k == 1:
      if d == 0 and len(n) != 1:
        return Anger(n[1:], k)
      elif d == 0 and len(n) == 1:
        return 0
      else:
        if len(n) != 1:
          S = d + 9 * (len(n) - 1)
          return S
        else:
          return d
    else:
      if d == 0:
        return Anger(n[1:], k)
      else:
        S = (d - 1) * (9 ** (k-1))
        for j in range(k-1):
          S *= len(n) - j - 1
          S //= j + 1
        T = 9 ** k
        for j in range(k):
          T *= len(n) - j - 1
          T //= j + 1
        return S + T + Anger(n[1:], k - 1)
    
print(Anger(N, K))

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    K = int(input())
    if N <= 1000:
        count = 0
        for i in range(1, N + 1):
            d = 0
            ci = i
            while ci > 0:
                d += (1 if ci % 10 > 0 else 0)
                ci //= 10
            if d == K: count += 1
        print(count)
    else:
        strN = str(N)
        dig = len(strN)
        DPsmall = [[0 for j in range(K + 1)] for i in range(dig)]
        DPsmall[0][0] = 1
        DPsmall[0][1] = int(strN[0]) - 1
        for i in range(1, dig):
            DPsmall[i][0] = 1
            for j in range(1, K + 1):
                DPsmall[i][j] += DPsmall[i-1][j-1] * 9 + DPsmall[i-1][j]
            
        DPlarge = [[0 for j in range(K + 1)] for i in range(dig)] #最初の桁がNの最初と一致
        DPlarge[0][0] = 1
        for i in range(1, dig):
            if strN[i] == "0": DPlarge[i][0] = DPlarge[i-1][0]
            else: DPlarge[i][0] = DPlarge[i-1][0] + 1
            for j in range(1, K + 1):
                if DPlarge[i-1][0] == j - 1: DPlarge[i][j] += (int(strN[i]) - 1 if strN[i] != "0" else 0)
                if DPlarge[i-1][0] == j: DPlarge[i][j] += (1 if strN[i] != "0" else 0)

                DPlarge[i][j] += DPlarge[i-1][j] #i桁目が0
                if j > 1: DPlarge[i][j] += DPlarge[i-1][j-1] * 9 #i桁目は0以上

        ans = DPsmall[dig-1][K] + DPlarge[dig-1][K]
        if DPlarge[dig-1][0] == K: ans += 1
        print(ans)   
        #print(DPsmall)
        #print(DPlarge)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
S = input().strip()
K = int(input())
N = len(S)
def cmb(n, r):
    nn = n
    rrr = r
    rr = 1
    for i in range(r):
        rr *= n
        n -= 1
    for i in range(r):
        rr //= r
        r -= 1
#    print(nn, rrr, rr)
    return rr

d = dict()
def f(k, i):
    if (k, i) in d:
        return d[(k, i)]
    if i == N:
        if k==0:
            return 1
        else:
            return 0
    dd = int(S[i])
    if k!=0:
        if dd == 0:
            rn = 0
            rm = 0
            r0 = f(k, i+1)
        else:
            rn = (dd-1)*cmb(N-i-1, k-1)*(9**(k-1))
            rm = f(k-1, i+1)
            r0 = cmb(N-i-1, k)*(9**k)
    else:
        rn = 0
        rm = 0
        r0 = f(k, i+1)
    d[(k,i)] = rm+rn+r0
#    print(k,i,rm,rn,r0)
    return rm + rn + r0

print(f(K, 0))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

# Python Program to find the count of 
# numbers in a range where the number 
# does not contain more than K non 
# zero digits 
  
# This function returns the count of 
# required numbers from 0 to num 
def countInRangeUtil(pos, cnt, tight, num, K): 
  
    # Last position 
    if pos == len(num): 
  
        # If count of non zero digits 
        # is less than or equal to K 
        if cnt == K: 
            return 1
        return 0
  
    # If this result is already computed 
    # simply return it 
    if dp[pos][cnt][tight] != -1: 
        return dp[pos][cnt][tight] 
  
    ans = 0
  
    # Maximum limit upto which we can place 
    # digit. If tight is 1, means number has 
    # already become smaller so we can place 
    # any digit, otherwise num[pos] 
    limit = 9 if tight else num[pos] 
  
    for dig in range(limit + 1): 
        currCnt = cnt 
  
        # If the current digit is nonzero 
        # increment currCnt 
        if dig != 0: 
            currCnt += 1
  
        currTight = tight 
  
        # At this position, number becomes 
        # smaller 
        if dig < num[pos]: 
            currTight = 1
  
        # Next recursive call 
        ans += countInRangeUtil(pos + 1, currCnt, currTight, num, K) 
  
    dp[pos][cnt][tight] = ans 
    return dp[pos][cnt][tight] 
  
# This function converts a number into its 
# digit vector and uses above function to compute 
# the answer 
def countInRange(x, K): 
    global dp, M 
  
    num = [] 
    while x: 
        num.append(x % 10) 
        x //= 10
  
    num.reverse() 
  
    # Initialize dp 
    dp = [[[-1, -1] for i in range(M)] for j in range(M)] 
    return countInRangeUtil(0, 0, 0, num, K) 

def solve(N: int, K: int):
    ans = countInRange(N, K) - countInRange(0, K)
    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
dp = []
M = 100

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, K)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from scipy.misc import comb

def f(n_str, k):
  while len(n_str) > 0 and n_str[0] == '0':
    n_str = n_str[1:]
  if len(n_str) < k:
    return 0
  if k == 1:
    return int(n_str[0]) + 9 * (len(n_str) - 1)
  else:
    return (int(n_str[0]) - 1) * f('9' * (len(n_str) - 1), k - 1) + f(n_str[1:], k - 1) + 9 ** k * (comb(len(n_str) - 1, k, exact=True) if len(n_str) > k else 0)

n = input()
k = int(input())

print(f(n, k))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from collections import deque

def comb(a, b):
    result = 1
    for i in range(b):
        result *= (a - i) / (i + 1)
    return result

def zero_num(n, k):
    if k == 0:
        return 1
    if len(n) == 0:
        return 0
    if n[0] == 0:
        return zero_num(n[1:], k)

    rest = comb(len(n) - 1, k) * 9 ** k
    rest += (n[0]-1) * comb(len(n) - 1, k-1) * 9 ** (k-1)
    return int(rest + zero_num(n[1:], k-1))


def main():
    N = tuple(map(int, input()))
    K = int(input())

    print(zero_num(N, K))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import combinations
N = int(input())
K = int(input())
s = []
n = N
while(N > 0):
    if N > 10:
        s.append(9)
    else:
        s.append(N-1)
    N = N // 10
ans = 0
for x in combinations(s, K):
    tmp = 1
    for i in range(K):
        tmp *= x[i]
    ans += tmp

if K == 1:
    print(ans + 1)
    exit(0)

for x in combinations(range(len(s)-1), K - 1):
    tmp = (10**(len(s)-1))*(s[-1]+1)
    for j in range(9, 0, -1):
        if K-1 == 2:
            for k in range(9, 0, -1):
                if tmp + ((10**x[1])*j) + ((10**x[0])*k) <= n:
                    ans += k
                    break

        elif K - 1 == 1:
            if tmp + ((10 ** x[0]) * j) <= n:
                ans += j
                break


print(ans)

Submission status: Accepted

Solution code:
# Python Program to find the count of 
# numbers in a range where the number 
# does not contain more than K non 
# zero digits 

# This function returns the count of 
# required numbers from 0 to num 
def countInRangeUtil(pos, cnt, tight, num): 

	# Last position 
	if pos == len(num): 

		# If count of non zero digits 
		# is less than or equal to K 
		if cnt == K: 
			return 1
		return 0

	# If this result is already computed 
	# simply return it 
	if dp[pos][cnt][tight] != -1: 
		return dp[pos][cnt][tight] 

	ans = 0

	# Maximum limit upto which we can place 
	# digit. If tight is 1, means number has 
	# already become smaller so we can place 
	# any digit, otherwise num[pos] 
	limit = 9 if tight else num[pos] 

	for dig in range(limit + 1): 
		currCnt = cnt 

		# If the current digit is nonzero 
		# increment currCnt 
		if dig != 0: 
			currCnt += 1

		currTight = tight 

		# At this position, number becomes 
		# smaller 
		if dig < num[pos]: 
			currTight = 1

		# Next recursive call 
		ans += countInRangeUtil(pos + 1, currCnt, currTight, num) 

	dp[pos][cnt][tight] = ans 
	return dp[pos][cnt][tight] 

# This function converts a number into its 
# digit vector and uses above function to compute 
# the answer 
def countInRange(x): 
	global dp, K, M 
	num = [] 
	while x: 
		num.append(x % 10) 
		x //= 10
	num.reverse() 
	dp = [[[-1, -1] for i in range(M)] for j in range(M)] 
	return countInRangeUtil(0, 0, 0, num) 

# Driver Code 

# states - position, count, tight 
dp = [] 
M = 101

# K is the number of non zero digits 
K = 0

L = 1
R = int(input())
K = int(input())
print(countInRange(R) - countInRange(L - 1))

Submission status: Accepted

Solution code:
n = int(input())
k = int(input())
def f(n,k):
  m = len(str(n))
  if n < 10^4:
    s = 0
    for i in range(1,n+1):
      if sum([1 for j in str(i) if j!="0"])==k:
        s += 1
  else:
    if k==1:
      s = n//(10**(m-1)) + 9*(m-1)
    elif k==2:
      s = (n//(10**(m-1))-1)*9*(m-1) + f(n%(10**(m-1)),1) + 9*9*(m-1)*(m-2)//2
    elif k==3:
      s = (n//(10**(m-1))-1)*9*9*(m-1)*(m-2)//2 + f(n%(10**(m-1)),2) + 9*9*9*(m-1)*(m-2)*(m-3)//6
  return s
print(f(n,k))

Submission status: Accepted

Solution code:
from itertools import combinations

def c(N, K):
    for i, n in enumerate(N):
        if n != 0:
            break
    N = N[i:]
    a = len(N)
    if a < K:
        return 0
    if K == 1:
        return N[0] + 9 * (a - 1)
    return (N[0] - 1) * c([9] * (a - 1), K - 1) + c(N[1:], K - 1) + c([9] * (a - 1), K)

def main():
    N = list(map(int, input()))
    K = int(input())
    return c(N, K)
    

print(main())

Submission status: Accepted

Solution code:
N = input()
n = int(N)
l = len(N)
k = int(input())
ans = 0
tmp = 0
def c(x,y):
  z = 1
  for w in range(y):
    z *= x - w
    z /= y - w
  return z
#print(c(5,2))
for i in range(l):
  for d in range(10):
    if d < int(N[i]):
      if d == 0 and k - tmp >= 0:
        now = c(l-1-i,k-tmp) * 9**(k-tmp)
        ans += now
        #print(i,d,now,l-1-i,k-tmp)
      elif k - tmp - 1 >= 0:
        now =  c(l-1-i,k-tmp-1) * 9**(k-tmp-1)
        ans += now
        #print(i,d,now,l-1-i,k-tmp-1)
    elif d == int(N[i]):
      if d != 0:
        tmp += 1
if k == tmp:
  ans += 1
print(int(ans))

Submission status: Accepted

Solution code:
N=input()
k=int(input())
ln=len(N)
DP=[[[0]*2 for _ in range(k+1)] for _ in range(len(N)+1)]
DP[0][0][0]=1
for i in range(1,len(N)+1):
  DP[i][0][1]=1
for i in range(len(N)):
  ni=int(N[i])
  for j in range(1,k+1):
    DP[i+1][j][1]=DP[i][j][1]+max(0,ni-1)*DP[i][j-1][0]+9*DP[i][j-1][1]
    if ni==0:
      DP[i+1][j][0]=DP[i][j][0]
    else:
      DP[i+1][j][0]=DP[i][j-1][0]
      DP[i+1][j][1]+=DP[i][j][0]
print(DP[ln][k][0]+DP[ln][k][1])

Submission status: Accepted

Solution code:
def main(N,K):

    if K == 1:
        return int(N[0]) + 9 * (len(N)-1)
    if K == 2:
        if len(N) == 1:
            return 0
        less = (len(N)-1) * (len(N)-2) // 2 * 9 * 9
        mid = (len(N)-1) * 9 * (int(N[0])-1)
        for i in range(1,len(N)):
            if N[i] != "0":
                break
        one = main(N[i:],1)
        return less+mid+one
    if K == 3:
        if len(N) < 3:
            return 0
    less = (len(N)-1) * (len(N)-2) * (len(N)-3) // 6 * 9 * 9 * 9
    mid = (int(N[0])-1) * (len(N)-1) * (len(N)-2) // 2 * 9 * 9
    for i in range(1,len(N)):
        if N[i] != "0":
            break
    one = main(N[i:],2)
    return (less+mid+one)
        
print(main(input(),int(input())))

Submission status: Accepted

Solution code:
N = input()
K = int(input())
l = len(N)
if K == 1:
    a = int(N[0])
    ans1 = 9*(l-1)+a
if K == 2:
    a=int(N[0])
    ans2 =(a-1)*9*(l-1)
    state = 0
    for n in N[1:]:
        if state:
            ans2 += 9
            continue
        if int(n) != 0:
            state = 1
        n = int(n)
        ans2 += n
    for i in range(2,l):
        ans2 += 81*(i-1)
    if l < K:
        ans2 = 0
if K == 3:
    a = int(N[0])
    ans3 = (a-1)*81*(l-1)*(l-2)/2
    state = 0
    for i in range(1,l):
        n = int(N[i])
        if state:
            ans3 += 81*(l-i-1)
            continue
        if n !=0:
            state = 1
        else:
            continue
        S = 0
        for j in range(i+1,l):
            m = int(N[j])
            if S:
                ans3 += n*9
                continue
            if m != 0:
                S = 1
            ans3 += (n-1)*9+m
    for i in range(3,l):
        ans3 += 729*(i-1)*(i-2)/2
    if l < K:
        ans3 = 0
if K == 1:
    print(ans1)
if K == 2:
    print(int(ans2))
if K == 3:
    print(int(ans3))

Submission status: Accepted

Solution code:
from math import factorial

def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

n = int(input())
k = int(input())


ans = 0

if len(str(n)) < k:
    print(0)
    exit()

def ans1(n,k):
    global ans
    m = len(str(n))
    if m-1 >= k:
        ans += combinations_count(m-1, k) * 9 ** k

    if m >= k:
        ans += (int(str(n)[0])-1) * combinations_count(m-1, k-1) * 9 ** (k-1)
        if k >= 2 and m > 1:
            ans1(int(str(n)[1:]), k-1)
        elif k == 1:
            ans += 1

ans1(n,k)

print(ans)

Submission status: Accepted

Solution code:
import itertools

def comb(a,b):
    if a<=0:
        return 0
    if b==1:
        return a
    elif b==2:
        return a*(a-1)//2
    else:
        return a*(a-1)*(a-2)//6

def tmp(L, K):
    ret=[]
    if K==1:
        bases=itertools.combinations(range(L+1),K)    
        for b in bases:
            ret+=[ k*10**b[0] for k in range(1,10)]
    if K==2:
        bases=itertools.combinations(range(L+1),K)
        kk=list(itertools.product(range(1,10),range(1,10)))
        for b in bases:
            ret+=[ k[0]*10**b[0] + k[1]*10**b[1] for k in kk]
    return ret

Nst=input()
K=int(input())
L=len(Nst)
N1=int(Nst[0])

if K==1:
    ans=comb( L-1, K) * 9 + N1
elif K>=2:
    ans=comb( L-1, K) * 9**(K) + comb( L-1, K-1) * 9**(K-1) *(N1-1)
    lst=[ 10**(L-1)*N1 + a for a in tmp(L-1, K-1)]
    ans+=sum([x <= int(Nst) for x in lst])
print (ans)

Submission status: Accepted

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

    def digit_dp(n):  # n は文字列で与える
        """n 以下の非負整数で、0でない数字がちょうど K 個あるような数の個数"""
        digit = len(n)

        dp = [[[0] * (K + 2) for j in range(2)] for i in range(digit + 1)]
        dp[0][0][0] = 1
        for i in range(digit):
            for j in range(2):
                for k in range(K + 1):
                    lim = 9 if j == 1 else ord(n[i]) - ord('0')
                    for d in range(lim + 1):
                        if d != 0:
                            t = k + 1
                            if t >= K + 2:
                                t = K + 1
                        else:
                            t = k
                        dp[i + 1][j or (d < lim)][t] += dp[i][j][k]
        return sum(dp[digit][j][K] for j in range(2))
    return digit_dp(N)

print(e_almost_everywhere_zero())

Submission status: Accepted

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

# dp[i][j][smaller] := i 桁目まで追加して, 0の個数がj個の数字の個数
keta = len(N)

dp = [[[0] * 2 for _ in range(K+3)] for __ in range(keta + 1)]

dp[0][0][0] = 1

for i in range(keta):
    now_digit = int(N[i])
    for k in range(10):
        for j in range(K+1):
            if k == 0:
                if k < now_digit:
                    dp[i+1][j][1] += dp[i][j][1] + dp[i][j][0]
                elif k == now_digit:
                    dp[i+1][j][1] += dp[i][j][1]
                    dp[i+1][j][0] += dp[i][j][0]
                else:
                    dp[i+1][j][1] += dp[i][j][1]
            else:
                if k < now_digit:
                    dp[i+1][j+1][1] += dp[i][j][1] + dp[i][j][0]
                elif k == now_digit:
                    dp[i+1][j+1][1] += dp[i][j][1]
                    dp[i+1][j+1][0] += dp[i][j][0]
                else:
                    dp[i+1][j+1][1] += dp[i][j][1]
print(dp[-1][K][0] + dp[-1][K][1])