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:
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:
        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:
        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: Runtime Error

Solution code:
import math
N = len(str(input()))
K = int(input())
print((math.factorial(N) // (math.factorial(N-K) * math.factorial(K)))*(9**K))

Submission status: Runtime Error

Solution code:
import sys

def comb(n, r):
    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:
        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:
        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: Runtime Error

Solution code:



#gcdは3.4.3だとfractionsにある
from fractions import gcd
import math

from math import factorial as f

from math import ceil,floor,sqrt


import bisect
import re
import heapq


from copy import deepcopy
import itertools

from sys import exit

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

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



def main():
    s = list(input())
    n = len(s)
    k = ii()
    ans = 0

    if n == k:
        for i in range(n):
            ans+= pow(9,k-i-1)*(int(s[i])-1)
        ans+=1
        print(ans)
        exit()




    for i in range(k):
        tmp = int(s[i])
        if i == 0:
            ans+=pow(9,k)*com(n-1,k)
 #           print(n-1,k-1)
            ans+=pow(9,k-1)*com(n-1,k-1)*(tmp-1)
 #           print(i,ans)
        else:
            ans+=pow(9,k-i)*com(n-1-i,k-i)
            if tmp > 0:
                ans+=pow(9,k-i-1)*com(n-1-i,k-i-1)*(tmp-1)
#            print(i,ans)
    ans+=1
    print(ans)





main()

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

answer=0

n=int(input())
k=int(input())
#keta=math.floor(math.log(n, 10))
now=n
keta=0
while now!=0:
    now=now//10
    keta+=1
keta-=1

moto=10**keta
first=n//moto
if k>=2:
    second=(n-first*moto)//(moto//10)
    if k>=3:
        third=(n-first*moto-second*(moto//10))//(moto//100)
#print(keta)
#print(first, second)
if keta>=k:
    answer+=cmb(keta, k)*(9**k)
answer+=max(first-1, 0)*cmb(keta, k-1)*(9**(k-1))
#print(answer)
if k==1:
    answer+=1
elif k==2:
    if keta>=k:
        answer+=cmb(keta-1, k-1)*(9**(k-1))
    answer+=cmb(keta-1, k-2)*max(second-1, 0)*(9**(k-2))
    if keta>=k:
        answer+=cmb(keta-2, k-2)*(9**(k-2))
    else:
        answer+=1
else:
    if keta>=k:
        answer+=cmb(keta-1, k-1)*(9**(k-1))
    answer+=cmb(keta-1, k-2)*max(second-1, 0)*(9**(k-2))
    if keta>=k:
        answer+=cmb(keta-2, k-2)*(9**(k-2))
    if keta>=k:
        answer+=third
    else:
        answer+=1

print(answer)

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N = I()
K = I()

S = str(N)
bl = len(S)

if K==1:
    print(int(S[0])+9*(bl-1))

if K==2:
    # 最上位bitに0
    if bl>=2:
        ans += (bl-1)*(bl-2)*81 // 2
    # 最上位bitに1~(その数未満)
    ans = (int(S[0])-1)*9*(bl-1)
    # 最上位bitにその数
    flag = False
    for s in S[1:]:
        if flag:
            ans += 9
        else:
            if s!='0':
                flag = True
                ans += int(s)
    print(ans)

if K==3:
    ans = 0
    # 最上位bitに0
    if bl>=3:
        ans += (bl-1)*(bl-2)*(bl-3)*9*9*9 //6
    # 最上位bitに1~（その数未満）
    if bl>=2:
        ans += (int(S[0])-1)*(bl-1)*(bl-2)*81 // 2
    # 最上位bitにその数
    S = S[1:]
    bl = len(S)
    ans += (int(S[0])-1)*9*(bl-1)
    flag = False
    for s in S[1:]:
        if flag:
            ans += 9
        else:
            if s!='0':
                flag = True
                ans += int(s)
    if bl>=2:
        ans += (bl-1)*(bl-2)*81 // 2
    print(ans)

Submission status: Runtime Error

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

def solve1(n):
    l = len(n)
    if l > 0:
        return int(n[0]) + 9 * (l-1)
    else:
        return 0

def solve2(n):
    l = len(n)
    if l > 1:
        ret = (int(n[0]) - 1) * 9 * (l-1) + 9 * 9 * (l - 1) * (l - 2)  // 2
        n = n[1:]
        while (n[0] == "0"):
            n = n[1:]
            if (n == "0"):
                n = ""
                break
        return ret + solve1(n)
    else:
        return 0

def solve3(n):
    l = len(n)
    if l > 2:
        ret = (int(n[0])-1) * 9 * 9 * (l - 1) * (l - 2) // 2 + 9 * 9 * 9 * (l - 1) * (l - 2) * (l - 3) // 6
        n = n[1:]
        while (n[0] == "0"):
            n = n[1:]
            if (n == "0"):
                n = ""
                break
        return ret + solve2(n)
    else:
        return 0

if k == 1:
    print(solve1(n))
elif k == 2:
    print(solve2(n))
else:
    print(solve3(n))

Submission status: Runtime Error

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 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: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K):
    M = len(N)
    ans = 1
    for i in range(K):
        ans *= M - i
        ans //= i+1
        ans *= 9
    print(ans)
    if K >= 1:
        t = 9 - int(N[0])
        for i in range(K-1):
            t *= len(N) - 1 - i
            t //= i+1
            t *= 9
        ans -= t
    if K >= 2:
        t = 9 - int(N[1])
        for i in range(K-2):
            t *= len(N) - 2 - i
            t //= i+1
            t *= 9
        ans -= t
    if K >= 3:
        t = 9 - int(N[2])
        ans -= t
    return ans


def main():
    N = read_str()
    K = read_int()
    print(slv(N, K))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

def solve1(n):
    l = len(n)
    if l > 0:
        return int(n[0]) + 9 * (l-1)
    else:
        return 0

def solve2(n):
    l = len(n)
    if l > 1:
        ret = (int(n[0]) - 1) * 9 * (l-1) + 9 * 9 * (l - 1) * (l - 2)  // 2
        n = n[1:]
        while (n[0] == "0"):
            n = n[1:]
            if (n == "0"):
                n = ""
                break
        return ret + solve1(n)
    else:
        return 0

def solve3(n):
    l = len(n)
    if l > 2:
        ret = (int(n[0])-1) * 9 * 9 * (l - 1) * (l - 2) // 2 + 9 * 9 * 9 * (l - 1) * (l - 2) * (l - 3) // 6
        n = n[1:]
        while (n[0] == "0"):
            n = n[1:]
        return ret + solve2(n)
    else:
        return 0

if k == 1:
    print(solve1(n))
elif k == 2:
    print(solve2(n))
else:
    print(solve3(n))

Submission status: Runtime Error

Solution code:
N = input()
K = int(input())
def Anger(n, k):
  d = int(n[0])
  if k == 1:
    S = d + 9 * (len(n) - 1)
    return S
  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: Runtime Error

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

def solve1(n):
    l = len(n)
    if l > 0:
        return int(n[0]) + 9 * (l-1)
    else:
        return 0

def solve2(n):
    l = len(n)
    ret = (int(n[0]) - 1) * 9 * (l-1) + 9 * 9 * (l - 1) * (l - 2)  // 2
    n = n[1:]
    while (n[0] == "0"):
        n = n[1:]
        if (n == "0"):
            n = ""
            break
    return ret + solve1(n)

def solve3(n):
    l = len(n)
    ret = (int(n[0])-1) * 9 * 9 * (l - 1) * (l - 2) // 2 + 9 * 9 * 9 * (l - 1) * (l - 2) * (l - 3) // 6
    n = n[1:]
    while (n[0] == "0"):
        n = n[1:]
    return ret + solve2(n)

if k == 1:
    print(solve1(n))
elif k == 2:
    print(solve2(n))
else:
    print(solve3(n))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int k;
const int maxb = 200;
const int maxd = 200;
vector<int> bit;
ll dp[maxb][maxd];
ll dfs(int pos, int num, bool flag)
{
	if(pos == -1) return num == k;
	if(!flag && dp[pos][num] != -1) return dp[pos][num];
	ll ret = 0;
	int end = flag ? bit[pos] : 9;
	for(int i = 0; i <= end; ++i)
		ret += dfs(pos - 1, num + (i != 0), flag && (i == end));
	if(!flag) dp[pos][num] = ret;
	return ret;
}	
ll calc(string s)
{
	reverse(s.begin(), s.end());
	bit.clear();
	for(int i = 0; i < s.length(); ++i)
		bit.push_back(s[i] - '0');
	return dfs(bit.size() - 1, 0, 1);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	memset(dp, -1, sizeof(dp));
	string L;
	cin >> L >> k;
	cout << calc(L) << endl;
	return  0;
}

Submission status: Runtime Error

Solution code:
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

def calc(i, k):
    return comb(len(n) - i - 1, k) * 9 ** k

ans = 0
if len(n) == k:
    ans +=1

for i in range(len(n)):
    if len(n)-i > k:
        ans += calc(i, k)
    k -= 1
    if k < 0:
        break
    ans += (int(n[i]) - 1) * calc(i, k)

print(ans)

Submission status: Runtime Error

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

def solve1(n):
    l = len(n)
    if l > 0:
        return int(n[0]) + 9 * (l-1)
    else:
        return 0

def solve2(n):
    l = len(n)
    ret = (int(n[0]) - 1) * 9 * (l-1) + 9 * 9 * (l - 1) * (l - 2)  // 2
    n = n[1:]
    while (n[0] == "0"):
        n = n[1:]
    return ret + solve1(n)

def solve3(n):
    l = len(n)
    ret = (int(n[0])-1) * 9 * 9 * (l - 1) * (l - 2) // 2 + 9 * 9 * 9 * (l - 1) * (l - 2) * (l - 3) // 6
    n = n[1:]
    while (n[0] == "0"):
        n = n[1:]
    return ret + solve2(n)

if k == 1:
    print(solve1(n))
elif k == 2:
    print(solve2(n))
else:
    print(solve3(n))

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
P = list(map(int, input().split()))
Pe = [(i+1)/2 for i in P]

maxsum = -1
cur = sum(Pe[0:K])
maxsum = cur
for i in range(1, N-K+1):
    cur = cur - Pe[i-1] + Pe[i+K-1]
    if cur > maxsum:
        maxsum = cur

print(maxsum)

Submission status: Runtime Error

Solution code:
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
N = int(input())
K = int(input())
L = len(str(N))
S = str(N)
if K>L:
  print(0)
  import sys
  sys.exit()
if K==1:
  s = ['0']*L
  cnt = 0
  for i in range(L):
    for j in range(1,10):
      s[i] = str(j)
      x = ''.join(s)
      x = int(x)
      if x<=N:
        cnt += 1
      s[i] = '0'
elif K==2:
  s = ['0']*L
  cnt = 0
  for i in range(L-1):
    for j in range(i+1,L):
      for a in range(1,10):
        for b in range(1,10):
          s[i] = str(a)
          s[j] = str(b)
          x = ''.join(s)
          x = int(x)
          if x<=N:
            cnt += 1
          s[i] = '0'
          s[j] = '0'
else:
  s = ['0']*L
  cnt = 0
  cnt += cmb(L-1,3)*(9**3)
  g = int(S[0])
  s[0] = S[0]
  for i in range(L-2):
    for j in range(i+1, L-1):
      for a in range(1,10):
        for b in range(1,10):
          s[j] = str(a)
          s[i] = str(b)
          x = ''.join(s)
          x = int(x)
          if x<=N:
            cnt += g
          else:
            cnt += g-1
          s[i] = '0'
          s[j] = '0'
print(cnt)

Submission status: Runtime Error

Solution code:
from math import factorial
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


# show_flg = False
show_flg = True


def main():
    s = S()
    K = I()
    N = len(s)
    n = [int(s[i]) for i in range(N)]
    dp = [[[0 for j in range(N + 2)]
           for smaller in range(2)]
          for i in range(N + 1)]
    dp[0][0][0] = 1

    for i in range(0, N):
        for smaller in range(2):
            for k in range(K + 1):
                for x in range(10 if smaller else n[i]+1):
                    if x != 0:
                        # print(i, smaller, k, k + 1)
                        dp[i+1][smaller or x < n[i]][k+1] += dp[i][smaller][k]
                    else:
                        dp[i+1][smaller or x < n[i]][k] += dp[i][smaller][k]
        # print(i, dp[i+1])

    # print(dp[N])
    print(dp[N][0][K] + dp[N][1][K])
    # print(C(2 * m + n - 1, 2*m) % MOD)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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)


if __name__ == "__main__":
    dp = []
    M = 20
    K = 0

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

Submission status: Runtime Error

Solution code:
n = input()
k = int(input())
m = len(n)
if k == 1:
    print(int(n[0])+9*(m-1))
elif k == 2:
    if m<2:ans = 0
    else:
        ans = 81*(m-1)*(m-2)//2
        ans += (int(n[0])-1)*(m-1)*9+int(n[1])+(m-2)*9
    print(ans)
else:
    if m<3:ans = 0
    else:
        ans1 = (m-1)*(m-2)*(m-3)//6*9**3
        ans2=(int(n[0])-1)*(m-1)*(m-2)//2*81
        ans3 =(m-2)*(m-3)//2*81
        ans = ans1+ans2+ans3
        if int(n[1]) > 0:
            ans += (int(n[1])-1)*(m-2)*9 + (m-3)*9+int(n[3])
    print(ans)

Submission status: Runtime Error

Solution code:
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
N = int(input())
K = int(input())
L = len(str(N))
S = str(N)
if K==1:
  s = ['0']*L
  cnt = 0
  for i in range(L):
    for j in range(1,10):
      s[i] = str(j)
      x = ''.join(s)
      x = int(x)
      if x<=N:
        cnt += 1
elif K==2:
  s = ['0']*L
  cnt = 0
  for i in range(L-1):
    for j in range(i+1,L):
      for a in range(1,10):
        for b in range(1,10):
          s[i] = str(a)
          s[j] = str(b)
          x = ''.join(s)
          x = int(x)
          if x<=N:
            cnt += 1
else:
  s = ['0']*L
  cnt = 0
  cnt += cmb(L-1,3)*(9**3)
  for i in range(L-2):
    for j in range(i+1, L-1):
      for a in range(1,10):
        for b in range(1,10):
          for c in range(1,10):
            s[0] = str(a)
            s[i] = str(b)
            s[j] = str(c)
            x = ''.join(s)
            x = int(x)
            if x<=N:
              cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
def main():
    S = input()
    N = len(S)
    K = int(input())
    dp = [[[0]*(N+1) for j in range(2)] for i in range(N+1)]
    dp[0][0][0] = 1
    for i in range(N):
        for j in range(2):
            for k in range(N):
                lim = (9 if j else int(S[i]))
                for d in range(lim + 1):
                    dp[i+1][j or d < lim][k + (d != 0)] += dp[i][j][k]
    ans = 0
    for j in range(2):
        ans += dp[N][j][K]
    print(ans)


if __name__ == '__main__':
    main()