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:

#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = list(list(map(int, list(input()))))
	K = int(input())
	
	#桁DP
	M = len(N)
	DP = [[[0] * 4 for i in range(M)] for j in range(2)]
	#最初の処理
	DP[0][0][1] = 1
	DP[1][0][1] = N[0] - 1
	for i in range(1, M):
		if N[i] == 0:
			DP[0][i][1] += DP[0][i - 1][1]
			DP[0][i][2] += DP[0][i - 1][2]
			DP[0][i][3] += DP[0][i - 1][3]

			DP[1][i][1] += DP[1][i - 1][1]
			DP[1][i][2] += DP[1][i - 1][1] * 9 + DP[1][i - 1][2]
			DP[1][i][3] += DP[1][i - 1][2] * 9 + DP[1][i - 1][3]
		else:
			DP[0][i][2] += DP[0][i - 1][1]
			DP[0][i][3] += DP[0][i - 1][2]

			DP[1][i][2] += DP[0][i - 1][1] * (N[i] - 1)
			DP[1][i][3] += DP[0][i - 1][2] * (N[i] - 1)
			DP[1][i][1] += DP[0][i - 1][1]
			DP[1][i][2] += DP[0][i - 1][2]
			DP[1][i][3] += DP[0][i - 1][3]

			DP[1][i][1] += DP[1][i - 1][1]
			DP[1][i][2] += DP[1][i - 1][1] * 9 + DP[1][i - 1][2]
			DP[1][i][3] += DP[1][i - 1][2] * 9 + DP[1][i - 1][3]
		DP[1][i][1] += 9

	ans = DP[0][M - 1][K] + DP[1][M - 1][K]
	# print(DP)
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
def two(n):
  n = str(n)
  top = int(n[0])
  b = len(n) - 1
  ans = b * (b-1) // 2 * 81 + (top-1) * b * 9 
  if b == 0:
    return 0
  for k,i in enumerate(n[1:],1):
    i = int(i)
    if i:
      ans += i + (b - k) * 9
      break
  return ans

n = int(input())
k = int(input())
if k == 1:
  n = str(n)
  top = int(n[0])
  ans = (len(n)-1) * 9 + top
  print(ans)
elif k == 2:
  n = str(n)
  top = int(n[0])
  b = len(n) - 1
  ans = b * (b-1) // 2 * 81 + (top-1) * b * 9 
  if b == 0:
    print(0)
    exit()
  for k,i in enumerate(n[1:],1):
    i = int(i)
    if i:
      ans += i + (b - k) * 9
      break
  print(ans)
elif k == 3:
  n = str(n)
  top = int(n[0])
  b = len(n) - 1
  if b <= 1:
    print(0)
    exit()
  ans = b * (b-1) * (b-2) // 6 * 729 + (top-1) * b * (b-1) // 2 *81
  n = int(n)
  t = n % (top * (10 ** b))
  mini_ans = two(t)
  ans += mini_ans
  print(ans)

Submission status: Accepted

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

def countInRangeUtil(pos, cnt, tight, num): 
    if pos == len(num): 
        if cnt == K: 
            return 1
        return 0
    if dp[pos][cnt][tight] != -1: 
        return dp[pos][cnt][tight] 
    ans = 0
    limit = 9 if tight else num[pos] 
    for dig in range(limit + 1): 
        currCnt = cnt 
        if dig != 0: 
            currCnt += 1
        currTight = tight 
        if dig < num[pos]: 
            currTight = 1
        ans += countInRangeUtil(pos + 1, currCnt, currTight, num) 
    dp[pos][cnt][tight] = ans 
    return dp[pos][cnt][tight] 
  
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)

dp = []
M = 101
print(countInRange(N))

Submission status: Accepted

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

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

LN = len(str(N))

def keta1(n):
    s = str(n)
    return (len(s) - 1) * 9 + int(s[0])
#print(keta1(N))


def keta2(n):
    if n < 10:
        return 0
    cnt2 = [0] * 101
    for i in range(2, 101):
        cnt2[i] = 9 * 9 * (i - 1)
    tmp2 = 0
    for i in range(len(str(n))):
        tmp2 += cnt2[i]
    tmp2 += (int(str(n)[0]) - 1) * keta1((10 ** (len(str(n))  - 1)) - 1) + keta1(int(str(n)[1:]))
    return tmp2

def keta3(n):
    cnt3 = [0] * 101
    for i in range(3, 101):
        cnt3[i] = 9 * 9 * 9 * (i - 1) * (i - 2) // 2
    tmp3 = 0
    for i in range(len(str(n))):
        tmp3 += cnt3[i]
    tmp3 += (int(str(N)[0]) - 1) * keta2((10 ** (len(str(n))  - 1)) - 1) + keta2(int(str(n)[1:]))
    
    return tmp3

if K == 1:
    print(keta1(N))
elif K == 2:
    print(keta2(N))
elif K == 3:
    print(keta3(N))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
k=int(input())

def sol1(n):
    l=len(str(n))
    #print(int(str(n)[0])+9*(l-1))
    return int(str(n)[0])+9*(l-1)

def sol2(n):
    ret=0
    a=int(str(n)[0])
    l=len(str(n))-1
    ret+=sol1(n-a*10**l)
    ret+=(a-1)*sol1(10**l-1)
    ret+=9*9*l*(l-1)//2
    return ret

def sol3(n):
    ret=0
    a=int(str(n)[0])
    l=len(str(n))-1
    ret+=sol2(n-a*10**l)
    ret+=(a-1)*sol2(10**l-1)
    ret+=9*9*9*l*(l-1)*(l-2)//6
    return ret


if k==1:
    print(sol1(n))
elif k==2:
    print(sol2(n))
elif k==3:
    print(sol3(n))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = str(I())
K = I()
digit_len = len(n)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(digit_len + 1)]
dp[0][0][0] = 1
for i in range(digit_len):
    d = int(n[i])
    for j in range(2):
        for k in range(K + 1):
            for l in range(10 if j else d + 1):
                if k + bool(l) <= K:
                    dp[i + 1][j or (l < d)][k + bool(l)] += dp[i][j][k]



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

Submission status: Accepted

Solution code:
def fact(n):
    x = 1
    for i in range(1, n + 1):
        x *= i
    return x


def nCr(n, r):
    return fact(n) // (fact(n - r) * fact(r))


def solve(N, K):
    if N < int("1" * K):
        return 0
    digits = [int(c) for c in str(N)]
    places = len(digits)
    count = 0
    for i in range(K - 1, places):
        # first digit then choose K-1 more places each 1-9
        firstChoice = 9
        if i == places - 1:
            # handle digits[0] case separate
            firstChoice = digits[0] - 1
        count += firstChoice * (9 ** (K - 1)) * nCr(i, K - 1)
    # digits[0] case
    if K == 1:
        count += 1
    else:
        count += solve(int("".join(map(str, digits[1:]))), K - 1)
    return count


N, = list(map(int, input().split()))
K, = list(map(int, input().split()))

print(solve(N, K))

Submission status: Accepted

Solution code:
import sys
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = input()
digit = len(N)
K = I()

# dp[i番目まで][未満かどうか][他の条件]
dp = [[[0]*(K+2) for _ in range(2)] for _ in range(digit+2)]
dp[0][0][0] = 1

for i in range(digit):
  num = int(N[i])
  for j in range(2):
    for k in range(K+2):
      for n in range(9+1 if j else num+1):
        dp[i + 1][j or (n < num)][min(K+1, k + (n != 0))] += dp[i][j][k]
print(dp[digit][0][K] + dp[digit][1][K])

Submission status: Accepted

Solution code:
def comb(n, k):
    ans = 1
    for i in range(k):
        ans *= (n-i)
    for i in range(k):
        ans //= (k-i)
    return ans

def count(n, k):
    if len(n) < k:
        return 0
    if k == 0:
        return 1
    if int(n) == 0:
        return 0
    if n[0] == "0":
        return count(n[1:], k)
    return count(n[1:], k-1) + comb(len(n)-1, k)*9**(k) + (int(n[0])-1)*comb(len(n)-1, k-1)*9**(k-1)

n = input()
k = int(input())
print(count(n, k))

Submission status: Accepted

Solution code:
import itertools
S=input()
SS=int(S)
N=len(S)
K=int(input())
def base9(n):
    res=""
    while(n>0):
        res=str((n%9)+1)+res
        n=n//9
    return "1"*(K-len(res))+res
ans=0
for seq in itertools.combinations(range(N),K):
    #print(seq,ans)
    low=0
    high=-1+9**K
    tmp=sum([9*10**(seq[i]) for i in range(K)])
    #print(tmp,SS)
    if tmp<=SS:
        ans+=9**K
        continue
    if tmp//9>SS:
        continue
    while(high-low>1):
        mid=(high+low)//2
        tmp2=base9(mid)
        tmp=sum([int(tmp2[i])*10**(seq[-i-1]) for i in range(K)])
        #print(tmp,tmp2,SS,low,mid,high)
        if tmp<=SS:
            low=mid
        else:
            high=mid
    ans+=low+1
print(ans)

Submission status: Accepted

Solution code:
import sys

def comb(n, r):
    if r > n or r < 0: return 0
    r = min(r, n - r)
    if r == 0: return 1
    if r == 1: return n
    numerator = list(range(n-r+1, n+1))
    denominator = list(range(1, r+1))
    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

n, k = map(int, sys.stdin.read().split())

def solve(n, k):
    p = int(str(n)[0])
    l = len(str(n))

    if k == 1:
        return 9 * (l - 1) + p
    
    elif k == 2:
        if l <= 1:
            return 0
        res = 0
        for i in range(1, l-1):
            res += comb(i, 1) * 9 * 9
        res += comb(l-1, 1) * 9 * (p - 1)
        res += solve(int(str(n)[1:]), 1)
        return res
    
    elif k == 3:
        if l <= 2:
            return 0
        res = 0
        for i in range(2, l-1):
            res += comb(i, 2) * 9 ** 2 * 9
        res += comb(l-1, 2) * 9 ** 2 * (p - 1)
        res += solve(int(str(n)[1:]), 2)
        return res

def main():
    return solve(n, k)

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
def countInRangeUtil(pos, cnt, tight, num): 

	if pos == len(num): 

		if cnt == K: 
			return 1
		return 0

	if dp[pos][cnt][tight] != -1: 
		return dp[pos][cnt][tight] 

	ans = 0

	limit = 9 if tight else num[pos] 

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

		if dig != 0: 
			currCnt += 1

		currTight = tight 

		if dig < num[pos]: 
			currTight = 1

		ans += countInRangeUtil(pos + 1, currCnt, currTight, num) 

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

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) 

n = int(input())
K = int(input())
dp = []
M = 100
print(countInRange(n) - countInRange(0))

Submission status: Accepted

Solution code:
n = int(input())
k = int(input())
s = str(n)
d = len(s)
c = 0
if k == 1:
  c += 9*(d-1)
if k == 2:
  c += 9*9*(((d-1)*(d-2))//2)
if k == 3:
  c += 3*9*9*(((d-1)*(d-2)*(d-3))//2)
if k == 1:
  c +=  int(s[0])
  print(c)
  exit()
if k == 2:
  s0 = int(s[0])
  c += (s0-1)*9*(d-1)
  for i in range(1,d):
    if int(s[i]) != 0:
      si = int(s[i])
      c += si + 9*(d-i-1)
      break
  print(c)
  exit()
if k == 3:
  s0 = int(s[0])
  c += (s0-1)*9*9*((d-1)*(d-2)//2)
  mi = 0
  for i in range(1,d):
    if int(s[i]) != 0:
      si = int(s[i])
      c += (si-1)*9*(d-i-1)+9*9*(d-i-1)*(d-i-2)//2
      mi = i
      break
  if mi != 0:
    for j in range(mi+1,d):
      if int(s[j]) != 0:
        sj = int(s[j])
        c += sj + 9*(d-j-1)
        break
  print(c)
  exit()

Submission status: Accepted

Solution code:
n=int(input())
k=int(input())
l=len(str(n))
a=(l-1)*(l-2)*(l-3)//6*9**3
if k==2:
  a=(l-1)*(l-2)//2*9*9
elif k==1:
  a=(l-1)*9
sn=list(str(n))
c=0
for i in range(l):
  p=sn[i]
  if p != "0":
    if k-c == 3:
      a+=(l-i-1)*(l-i-2)//2*(int(p)-1)*9*9
    elif k-c == 2:
      a+=(l-i-1)*(int(p)-1)*9
      if not k==2:
        a+=(l-i-1)*(l-i-2)//2*9*9
    elif k-c == 1:
      a+=int(p)
      if not k==1:
        a+=(l-i-1)*9
    c+=1
    if c==k:
      break
print(a)

Submission status: Accepted

Solution code:
def countInRangeUtil(pos, cnt, tight, num):   
    if pos == len(num):   
        if cnt == K: 
            return 1
        return 0
  
    if dp[pos][cnt][tight] != -1: 
        return dp[pos][cnt][tight] 
  
    ans = 0
  
    limit = 9 if tight else num[pos] 
  
    for dig in range(limit + 1): 
        currCnt = cnt 
  
        if dig != 0: 
            currCnt += 1
  
        currTight = tight 
  
        if dig < num[pos]: 
            currTight = 1
  
        ans += countInRangeUtil(pos + 1, currCnt, currTight, num) 
  
    dp[pos][cnt][tight] = ans 
    return dp[pos][cnt][tight] 
  
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) 
  
dp = [] 
M = 100
N = int(input())
K = int(input())

print(countInRange(N))

Submission status: Accepted

Solution code:
import sys


TEST_INPUT = [
    """
    100
    1
    """,
    """
    25
    2
    """,
    """
    314159
    2
    """,
    """
    9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
    3
    """
]
ANSWER = [
    "19",
    "14",
    "937",
    "117879300"
]


class InputHandler:

    def __init__(self, text_lines="", is_test=False):
        self.data = list(text_lines.split("\n"))
        self.index = 0
        self.is_test = is_test

    def input(self):
        if self.is_test:
            self.index += 1
            return self.data[self.index].strip()
        else:
            return sys.stdin.readline().rstrip()


def solve(n, k):
    res = 0
    le = len(n) - 1

    # smaller order
    if k == 1 and le >= 1:
        res += 9 * le
    if k == 2 and le >= 2:
        res += 9 * 9 * le * (le - 1) // 2
    if k == 3 and le >= 3:
        res += 9 * 9 * 9 * le * (le - 1) * (le - 2) // 6

    # bxxxxx
    if k == 1:
        res += int(n[0]) - 1
    if k == 2:
        res += (int(n[0]) - 1) * (9 * le)
    if k == 3:
        res += (int(n[0]) - 1) * (9 * 9 * le * (le - 1) // 2)

    # axxxxx
    if k == 1:
        res += 1
    if k == 2:
        # first nonzero
        for i in range(1, le + 1):
            if int(n[i]) > 0:
                res += int(n[i])
                res += 9 * (le - i)
                break
    if k == 3:
        j = 0
        # first nonzero
        for i in range(1, le + 1):
            if int(n[i]) > 0:
                res += (int(n[i]) - 1) * 9 * (le - i)
                res += 9 * 9 * ((le - i) * (le - i - 1) // 2)
                j = i
                break
        # second nonzero
        for i in range(j + 1, le + 1):
            if int(n[i]) > 0:
                res += int(n[i])
                res += 9 * (le - i)
                break
    return res


def input_and_solve(ih):
    n = ih.input()
    k = int(ih.input())
    res = solve(n, k)
    return res


def main():
    ih = InputHandler()
    res = input_and_solve(ih)
    print(res)


def test():
    for test_input, ans in zip(TEST_INPUT, ANSWER):
        ih = InputHandler(test_input, True)
        res = input_and_solve(ih)
        # print(res, ans)
        assert str(res) == str(ans)


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

Solution code:
n=int(input())
k=int(input())
def k1(n):
    n_l=len(str(n))
    n_0=int(str(n)[0])
    return n_0+9*(n_l-1)
def k2(n):
    n_l=len(str(n))
    if n_l<=1:
        return 0
    n_0=int(str(n)[0])
    return 81*((n_l-1)*(n_l-2)//2)+(n_0-1)*9*(n_l-1)+k1(n%(10**(n_l-1)))
def k3(n):
    n_l=len(str(n))
    if n_l<=2:
        return 0
    n_0=int(str(n)[0])
    return 729*((n_l-1)*(n_l-2)*(n_l-3)//6)+(n_0-1)*81*((n_l-1)*(n_l-2)//2)+k2(n%(10**(n_l-1)))
if k==1:
    print(k1(n))
if k==2:
    print(k2(n))
if k==3:
    print(k3(n))

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() 

	# Initialize dp 
	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:

def mCk(m, k):
  if k == 3:
    return m * (m - 1) * (m - 2) // 6
  elif k == 2:
    return m * (m - 1) // 2
  elif k == 1:
    return m
  return None

def count_up(n, k):
  digit_n = len(n)
  if digit_n < k: #桁不足
    return 0
  top_n = int(n[0])
  if k == 1:
    return (top_n + 9 * (digit_n - 1))
  return (
    count_up(str(int(n[1:])), k - 1) 
    + (top_n - 1) * mCk(digit_n - 1, k - 1) * (9 ** (k - 1))
    + mCk(digit_n - 1, k) * (9 ** k)
  )


def main():
  n = input() 
  k = int(input())
  print(count_up(n, k))

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
def main():
    from itertools import combinations

    N = raw_input()
    K = int(raw_input())
    digit = len(N)
    N = int(N)


    ans = 0

    # １桁目を考慮しない
    ans += len(list(combinations(range(digit - 1), K))) * (9 ** K)

    if K == 3:
        # 同じ長さの数を考える
        for top in range(1, 10):
            if int(str(N)[0]) < top:
                continue

            if int(str(N)[0]) > top:
                ans += len(list(combinations(range(digit - 1), K - 1))) * (9 ** (K - 1))
                continue

            for perm_digit in combinations(range(1, digit), K - 1):
                perm_digit = list(perm_digit)
                for pn1 in range(1, 10):
                    for pn2 in range(1, 10):
                        s = ['0'] * digit
                        s[0] = str(top)
                        s[perm_digit[0]] = str(pn1)
                        s[perm_digit[1]] = str(pn2)

                        if int(''.join(s)) <= N:
                            ans += 1

    elif K == 2:
        # 同じ長さの数を考える
        for top in range(1, 10):
            for perm_digit in combinations(range(1, digit), K - 1):
                perm_digit = list(perm_digit)

                for pn1 in range(1, 10):
                    s = ['0'] * digit
                    s[0] = str(top)
                    s[perm_digit[0]] = str(pn1)
                    if int(''.join(s)) <= N:
                        ans += 1

    elif K == 1:
        ans += int(str(N)[0])

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
n=int(input())
k=int(input())
strn=str(n)

ans1=9*(len(strn)-1)+int(strn[0])
#print(ans1)

def fuc1(x):
    strn=str(x)
    return 9*(len(strn)-1)+int(strn[0])

def fuc2(x):
    if x<10:
        return 0
    strn=str(x)
    ans2=fuc1(int(strn[1:]))
    ans2+=(int(strn[0])-1)*(9*(len(strn)-1))
    #print(ans2,"q")
    for i in range(1,len(strn)-1):
        ans2+=9*(9*(len(strn)-i-1))
    return ans2

def fuc3(x):
    if x<100:
        return 0
    ans3=fuc2(int(strn[1:]))
    ans3+=(int(strn[0])-1)*(81*(len(strn)-1)*(len(strn)-2)//2)
    #print(ans3,"z")
    for i in range(1,len(strn)-2):
        ans3+=9*(81*(len(strn)-i-1)*(len(strn)-i-2)//2)
    #print(ans3)
    return ans3

if k==1:
    print(fuc1(n))
if k==2:
    print(fuc2(n))
if k==3:
    print(fuc3(n))

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, K = [int(sys.stdin.buffer.readline()) for _ in range(2)]
N = str(N)

DIGIT = len(N)
# d から K 個選ぶ
dp = np.zeros((DIGIT + 1, K + 1, 2), dtype=int)
dp[0, 0, 0] = 1
for d in range(1, DIGIT + 1):
    nd = int(N[d - 1])
    if nd > 0:
        dp[d, :, 1] += dp[d - 1, :, 0]
        dp[d, :, 1] += dp[d - 1, :, 1]
        for k in range(1, K + 1):
            # この d で 1 個使う
            dp[d][k][0] += dp[d - 1][k - 1][0]
            dp[d][k][1] += dp[d - 1][k - 1][0] * (nd - 1)
            dp[d][k][1] += dp[d - 1][k - 1][1] * 9
    else:
        dp[d, :, 0] += dp[d - 1, :, 0]
        dp[d, :, 1] += dp[d - 1, :, 1]
        for k in range(1, K + 1):
            # この d で 1 個使う
            dp[d][k][1] += dp[d - 1][k - 1][1] * 9
print(dp[-1][K].sum())

Submission status: Accepted

Solution code:
import sys
n = int(input())
k = int(input())
n_keta = len(str(n))
memo_ls = [[[0 for _k in range(2)] for j in range(k+2)] for i in range(n_keta + 1)] #フラグ1は小さいこと確定
memo_ls[0][0][0] = 1
for i, base in enumerate(str(n), 1):
    base = int(base)
    for j in range(10):
        for _k in range(k+1):
            if j > base:
                memo_ls[i][_k+1][1] += memo_ls[i-1][_k][1]
            elif j == base:
                if j == 0:
                    memo_ls[i][_k][0] += memo_ls[i-1][_k][0]
                    memo_ls[i][_k][1] += memo_ls[i - 1][_k][1]
                else:
                    memo_ls[i][_k+1][1] += memo_ls[i-1][_k][1]
                    memo_ls[i][_k+1][0] += memo_ls[i-1][_k][0]
            else:
                if j == 0:
                    memo_ls[i][_k][1] += memo_ls[i-1][_k][1] + memo_ls[i - 1][_k][0]
                else:
                    memo_ls[i][_k+1][1] += memo_ls[i-1][_k][1] + memo_ls[i-1][_k][0]
print(sum(memo_ls[-1][k]))

Submission status: Accepted

Solution code:
def main():
    N = input()
    K = int(input())
    t = len(N)
    if K == 1:
        return (t - 1) * 9 + int(N[0])
    elif K == 2:
        if t < 2:
            return 0
        r = (t - 1) * (t - 2) * 81 // 2
        r += (int(N[0]) - 1) * (t - 1) * 9
        for i, v in enumerate(N):
            if i < 1:
                continue
            if v != '0':
                r += int(v) + 9 * (t - 1 - i)
                return r
        return r
    else:
        if t < 3:
            return 0
        r = (t - 1) * (t - 2) * (t - 3) * 729// 6
        r += (int(N[0]) - 1) * (t - 1) * (t - 2) * 81 // 2
        second = False
        for i, v in enumerate(N):
            if i < 1:
                continue
            if v != '0' and not second:
                r += (int(v)-1) * (t - 1 - i) * 9
                r += (t - 1 - i) * (t - 2 - i) * 81 // 2
                second = True
            elif v != '0':
                r += int(v) + 9 * (t - 1 - i)
                return r
        return r
print(main())

Submission status: Accepted

Solution code:
def ans(n,k):
  s=str(n)
  a=len(s)
  b=int(s[0])
  if(n==0):
    return 0
  elif(k==1):
    return 9*(a-1)+b
  elif(k==2):
    return int(81*(a-1)*(a-2)/2)+9*(b-1)*(a-1)+ans(n-b*10**(a-1),1)
  else:
    return int(729*(a-1)*(a-2)*(a-3)/6)+int(81*(b-1)*(a-1)*(a-2)/2)+ans(n-b*10**(a-1),2)

N=int(input())
K=int(input())
print(ans(N,K))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
import pdb
     
def main():
    N = S()
    K = I()
    dp = [[[0 for _ in range(102)] for __ in range(2)] for ___ in range(102)]
    dp[0][0][0] = 1
    for i in range(1, len(N)+1):
        for j in range(2):
            if j == 1:
                max_dig = 9
            else:
                max_dig = int(N[i-1])
            for k in range(i+1):
                for d in range(max_dig + 1):
                    if d < max_dig:
                        # kakutei
                        miman = 1
                    else:
                        miman = 0
                        if j == 1:
                            miman = 1
                    if d != 0:
                        newK = k + 1
                    else:
                        newK = k
                    dp[i][miman][newK] += dp[i-1][j][k]

    print(dp[len(N)][0][K] + dp[len(N)][1][K])
main()

Submission status: Accepted

Solution code:
n=int(input())
K=int(input())
n_list=[]
while n>=10:
    n_list.append(n%10)
    n=(n-n%10)//10
n_list.append(n)
n_list.reverse()
x=len(n_list)
dp=[[[0]*100,[0]*100] for i in range(x+1)]
dp[0][1][0]=1
for i in range(x):
    for k in range(99):
        dp[i+1][0][k]+=dp[i][0][k]
        dp[i+1][0][k+1]+=dp[i][0][k]*9
    if n_list[i]==0:
        for k in range(99):
            dp[i+1][1][k]+=dp[i][1][k]
    else:
        n=n_list[i]
        for k in range(99):
            dp[i+1][1][k+1]+=dp[i][1][k]
            dp[i+1][0][k]+=dp[i][1][k]
            dp[i+1][0][k+1]+=dp[i][1][k]*(n-1)
ans=dp[x][0][K]+dp[x][1][K]
print(ans)

Submission status: Accepted

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

LEN=len(N)

from functools import lru_cache
@lru_cache(maxsize=None)
def dfs(keta,use,coin):
    ANS=0

    if keta==LEN:
        if use==K:
            return 1
        return 0
        
    if coin==0:
        if use<K:
            ANS+=dfs(keta+1,use+1,0)*9
        ANS+=dfs(keta+1,use,0)

        return ANS

    else:
        kn=int(N[keta])

        if kn==0:
            return dfs(keta+1,use,1)

        ANS+=dfs(keta+1,use,0)
        ANS+=dfs(keta+1,use+1,0)*(kn-1)
        ANS+=dfs(keta+1,use+1,1)

        return ANS

print(dfs(0,0,1))

Submission status: Accepted

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

dp = [[0] * 4 for _ in range(2)]
dp[0][1] = 1
dp[1][0] = 1
dp[1][1] = int(N[0]) - 1

for n in N[1:] :
  n = int(n)
  ndp = [[0] * 4 for _ in range(2)]
  
  if n == 0 :
    ndp[0] = dp[0]
  else :
    ndp[0][1] = dp[0][0]
    ndp[0][2] = dp[0][1]
    ndp[0][3] = dp[0][2]

  ndp[1][0] = dp[1][0]
  ndp[1][1] = dp[1][1] + dp[1][0] * 9
  ndp[1][2] = dp[1][2] + dp[1][1] * 9
  ndp[1][3] = dp[1][3] + dp[1][2] * 9
    
  if n != 0 :
    ndp[1][0] += dp[0][0]
    ndp[1][1] += dp[0][0] * (n - 1) + dp[0][1]
    ndp[1][2] += dp[0][1] * (n - 1) + dp[0][2]
    ndp[1][3] += dp[0][2] * (n - 1) + dp[0][3]
  
  dp = ndp
  
print(dp[0][K] + dp[1][K])

Submission status: Accepted

Solution code:
n = int(input())
k = int(input())
from math import log10, ceil


def helper(n, k):
    if k == 0:
        return 1
    if k >= 1 and n == 0:
        return 0

    keta = ceil(log10(n))
    if n == 10 ** (keta):
        keta += 1
    count = 0
    for tmp_keta in range(1, keta):
        if tmp_keta >= k:
            add_no = 9
            if k == 2:
                add_no *= 9 * (tmp_keta - 1)
            if k == 3:
                add_no *= 81 * int((tmp_keta - 2) * (tmp_keta - 1) / 2)
            count += add_no

    top = n // (10 ** (keta - 1))
    amari = n % (10 ** (keta - 1))
    if keta >= k:
        add_no = 1
        if k == 2:
            add_no *= 9 * (keta - 1)
        if k == 3:
            add_no *= 81 * int((keta - 2) * (keta - 1) / 2)
        count += add_no * (top - 1)
        count += helper(amari, k - 1)
    return count


print(helper(n, k))

# print(ceil(keta), top)

Submission status: Accepted

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

# 桁DP
# dp[桁数][未満フラグ][0じゃない数の数]
# 010みたいなときに頭の0を数えないよう注意（0を数えると面倒、0じゃないを数えれば問題なし）

dp=[[[0 for i in range(K+1)] for j in range(2)] for k in range(keta)]

# ある数が与えられたときに、その数未満で0じゃない数の値を返す
def getMiman(X):
  if X>0:
    return X-1
  else:
    return 0

x0=int(N[0])
# 未満じゃないのに先頭が0はあり得ない
dp[0][0][0]=0
# 未満で、0じゃない数が存在しないのは先頭から0の場合のみ
dp[0][1][0]=1
# 未満じゃなく、0でない数が1->元の数の場合なので1
dp[0][0][1]=1
# 未満で、0でない数が1　3の場合2,1
dp[0][1][1]=getMiman(x0)

for i in range(1,keta):
  # 全桁をDP
  x=int(N[i])
  # 未満じゃないのに0じゃない数が0個なのはあり得ない
  dp[i][0][0]=0
  # 未満で、0じゃない数が存在しないのはここまでずっと0だった場合のみ
  dp[i][1][0]=1
  for j in range(1,K+1):
    # 未満じゃなくて、0じゃない数がj個なのは以下の合計：
    # ・前の桁（未満じゃない）で0じゃない数がj-1個で、今回の桁が0じゃない場合
    # ・前の桁（未満じゃない）で0じゃない数がj個で、今回の桁が0
    dp[i][0][j]=dp[i-1][0][j-1]*(x!=0)+dp[i-1][0][j]*(x==0)
    
    # 未満で、0じゃない数がj個なのは以下の合計：
    # ・前の桁（未満じゃない）で0じゃない数がj-1個で、今回の桁が未満相当（getMiman）
    # ・前の桁（未満じゃない）で0じゃない数がj個で、今回の桁が0でない場合に0を選択する
    # ・前の桁（未満）で0じゃない数がj-1個で、今回は1-9まで選べるので9通り
    # ・前の桁（未満）で0じゃない数がj個で、今回は0を選ぶ
    dp[i][1][j]=dp[i-1][0][j-1]*getMiman(x)+dp[i-1][0][j]*(x!=0)+dp[i-1][1][j-1]*9+dp[i-1][1][j]*1
  
print(dp[keta-1][0][K]+dp[keta-1][1][K])