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:
from sys import stdin
from functools import lru_cache

@lru_cache(None)
def solver(N, K):
    """N以下で0でないものがちょうどK個。0を含める"""
    if N < 10:
        if K == 0:
            return 1
        if K == 1:
            return N
        return 0
    # divmod : 商と余りを両方取れる
    m, r = divmod(N,10)
    ans = 0
        # 1の位が nonzero
        ans += solver(m, K-1) * r
        ans += solver(m-1, K-1) * (9-r)
    ans += solver(m, K)
    return ans


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

Submission status: Runtime Error

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

dp = [[[0,0] for _ in range(4)] for _ in range(101)]

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

# i = Nの●桁目
# j = 0以外の数字を何回利用しているか
# k == 0 Nを超えないように注意が必要
# k == 1 N以下が保証されている

keta = len(str(N))
for i in range(keta):
  for j in range(4):
    for k in range(2):
      num = int(str(N)[i])

      for n in range(10):
        ni, nj, nk = i+1, j, k

        if n != 0:
          nj += 1 # 0以外の数字を利用した数が増えた
        if nj > K: 
          continue # すでにKを使い切っているときはカウントしない
        if k == 0:
          if n > num:
            continue # Nを超えているので飛ばす
          if n < num:
            nk = 1 # 何でもOK

        dp[ni][nj][nk] += dp[i][j][k]

print(dp[keta][K][0] + dp[keta][K][1])N = int(input())
K = int(input())

dp = [[[0,0] for _ in range(4)] for _ in range(101)]

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

# i = Nの●桁目
# j = 0以外の数字を何回利用しているか
# k == 0 Nを超えないように注意が必要
# k == 1 N以下が保証されている

keta = len(str(N))
for i in range(keta):
  for j in range(4):
    for k in range(2):
      num = int(str(N)[i])

      for n in range(10):
        ni, nj, nk = i+1, j, k

        if n != 0:
          nj += 1 # 0以外の数字を利用した数が増えた
        if nj > K: 
          continue # すでにKを使い切っているときはカウントしない
        if k == 0:
          if n > num:
            continue # Nを超えているので飛ばす
          if n < num:
            nk = 1 # 何でもOK

        dp[ni][nj][nk] += dp[i][j][k]

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

Submission status: Runtime Error

Solution code:
N = input()
K = int(input())
dp= [[[0]*2 for i in range(len(N)+1)] for _ in range(len(N)+1)]
dp[0][0][0]=1
for i in range(len(N)):
  for j in range(len(N)):
    if int(N[i])!=0:
      dp[i+1][j+1][1]+=dp[i][j][1]*9+dp[i][j][0]*(int(N[i])-1)
      dp[i+1][j][1] += dp[i][j][1]+dp[i][j][0]
      dp[i+1][j+1][0] += dp[i][j][0] 
    if int(N[i])==0:
      dp[i+1][j+1][1] += dp[i][j][1]*9
      dp[i+1][j][1] += dp[i][j][1]
      dp[i+1][j][0] += dp[i][j][0]
print(dp[len(N)][K][0]+dp[len(N)][K][1])

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#include <cstdlib> 
#include <math.h>
#define gap cout<<endl;
#define FOR(I, A, B) for (int I = (A); I <= (B); I++)
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair< int,int > ii;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fo(i,n) for(int i=0;i<n;i++)
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c)).begin() i = (c).begin(); i != (c).end(); i++)
#define INF 1<<30
#define present(c,x) ((c).find(x) != (c).end())
const int N=20000;
std::vector<int> fact(3000,1);
int k;
string n;
int pow(int a, int b)
{
    int ans=1;
    while(b)
    {
        if(b&1)
            ans=(ans*a);
        b/=2;
        a=(a*a);
    }
    return ans;
}
 
 
 
 
int nCr(int x, int y)
{
    if(y>x)
        return 0;
    if(y==0) return 1;
    if(x==y) return 1;
    if(x==0&&y==0) return 1;
    
     //cout<<x<<" "<<y<<endl;
    if(y==1) return x;
    if(y==2){
        return x*(x-1)/(2);
    }
    if(y==3){
        return x*(x-1)*(x-2)/(6);
    }
    return 1;
    //cout<<fact[]<<endl;
    //if(num2==0) cout<<x<<" "<<y<<endl;
    
}
int fu(string s,int k){
    if(k<=0) return 1;
    int len=sz(s);
    if(len==0) return 0;
    int tmp,tmp2,tmp3;
    tmp=tmp3=tmp2=0;
    //cout<<tmp<<endl;
    if(k>len) return 0;
    if(s[0]=='0') return fu(s.substr(1),k);
    if(s[0]>'0') tmp=nCr(len-1,k)*(pow(9,k));
    tmp3=(s[0]-'0'-1)*(nCr(len-1,k-1))*(pow(9,k-1));
    
    if(len>=1) {string s2=s.substr(1);
         tmp2=(fu(s2,k-1));}
     
 
    return tmp2+tmp3+tmp;
 
}
 
 
int main(){
    
     
    cin>>n>>k; 
    int ans=fu(n,k);
    cout<<ans<<endl;
}

Submission status: Runtime Error

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

DP=[[[0]*(k+1) for _ in range(2)] for _ in range(m+1)]
DP[0][0][0]=1

for i in range(1,m+1):
    for flag in range(2):
        num=9 if flag else int(n[i-1])
        for j in range(k+1):
            for k in range(num+1):
                if k!=0:
                    DP[i][flag or k<=num][j] +=DP[i-1][flag][j-1]
                else:
                    DP[i][flag or k<=num][j] +=DP[i-1][flag][j]
print(DP[-1][0][k]+DP[-1][1][k])

Submission status: Runtime Error

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

l = len(str(n))

if k == 1:
    r = int(str(n)[0])
    t = 9*(l-1)+r
elif k == 2:
    r, s = int(str(n)[0]), int(str(n)[1])
    t = 81*(l-1)*(l-2)//2 + 9*(r-1)*(l-1) + s + 9*(l-2)
else:
    r, s, u = int(str(n)[0]), int(str(n)[1]), int(str(n)[2])
    t = 729*(l-1)*(l-2)*(l-3)//6 + 81*(r-1)*(l-1)*(l-2)//2 + 81*(l-2)*(l-3)//2 + 9*(s-1)*(l-2) + 9*(l-3) + u
print(t)

Submission status: Runtime Error

Solution code:
n = int(input())
k = int(input())
number = []
while n:
    number.append(n%10)
    n//=10

from math import factorial
def comb(n,k):
    if n>=k:
        return int(factorial(n)/(factorial(k)*factorial(n-k)))
    else:
        return 0


t = len(number)
t1 = len(number) - 1
#if t>k:
   # ans = (9**k)*comb(t1,k) + (9**(k-1))*(number[t1]-1)*comb(t1,k-1)
#else:
 #   ans = (9**(k-1))*(number[t1]-1)*comb(t1,k-1)



ans = 0
def calc(a,k):
    t = len(a)
    t1 = len(a) - 1
    if k<1:
        return 0
    else:
        if a[t1]>0: #and t>1:
            ans = (9**k)*comb(t1,k) + (9**(k-1))*(a[t1]-1)*comb(t1,k-1)
        #elif a[t1]>0 and t==1:
           # ans = a[t1]
        else:
            ans = 0
        ans+=calc(a[:(t-1)],k-1)
        return ans
ans += calc(number,k)
if ans>=0:
    if number[-k]>=1:
        print(ans+1)
    else:
        print(ans)
else:
    print(0)

Submission status: Runtime Error

Solution code:
n = int(input())
k = int(input())
number = []
while n:
    number.append(n%10)
    n//=10

from math import factorial
def comb(n,k):
    if n>=k:
        return int(factorial(n)/(factorial(k)*factorial(n-k)))
    else:
        return 0


t = len(number)
t1 = len(number) - 1
#if t>k:
   # ans = (9**k)*comb(t1,k) + (9**(k-1))*(number[t1]-1)*comb(t1,k-1)
#else:
 #   ans = (9**(k-1))*(number[t1]-1)*comb(t1,k-1)



ans = 0
def calc(a,k):
    t = len(a)
    t1 = len(a) - 1
    if k<1:
        return 0
    else:
        if a[t1]>0: #and t>1:
            ans = (9**k)*comb(t1,k) + (9**(k-1))*(a[t1]-1)*comb(t1,k-1)
        #elif a[t1]>0 and t==1:
           # ans = a[t1]
        else:
            ans = 0
        ans+=calc(a[:(t-1)],k-1)
        return ans
ans += calc(number,k)
if ans>0:
    if number[-k]>=1:
        print(ans+1)
    else:
        print(ans)
else:
    print(0)

Submission status: Runtime Error

Solution code:
from math import factorial
N=int(input())
K=int(input())
#N,K = int(314159),int(3)
S = list(map(int,str(N)))

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

def D(i,j): 
    return (9**j)*C(i,j)

ans = 0
l = len(S)
for i in range(l):
    if K >= 1:
        ans = ans + (int(S[i])-1)*D(l-1,K-1) + D(l-1,K)
        K -= 1
        l -= 1
    else:
        ans += 1
        break
print(ans)

Submission status: Runtime Error

Solution code:
from math import factorial
N=int(input())
K=int(input())
#N,K = int(314159),int(3)
S = list(map(int,str(N)))

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

def D(i,j): 
    return (9**j)*C(i,j)

ans = 0
l = len(S)
for i in range(l):
    if K >= 1:
        print('K',K)
        print((int(S[i])-1)*D(l-1,K-1))
        print(D(l-1,K))
        ans = ans + (int(S[i])-1)*D(l-1,K-1) + D(l-1,K)
        K -= 1
        l -= 1
    else:
        ans += 1
        break
print(ans)

Submission status: Runtime Error

Solution code:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp6
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = Console.ReadLine();
            var K = Readint();
            var dpt1=Enumerable.Repeat(0, s.Length).Select(x => Enumerable.Repeat(0, K + 1).ToArray()).ToArray();
            var dpt2 = Enumerable.Repeat(0, s.Length).Select(x => Enumerable.Repeat(0, K + 1).ToArray()).ToArray();

            dpt1[0][1] = int.Parse(s[0].ToString()) - 1;
            dpt2[0][1] = 1;
            dpt1[0][0] = 1;

            foreach (var i in Enumerable.Range(1,s.Length-1))
            {
                var current = int.Parse(s[i].ToString());
                dpt1[i][0]=1;
                for(int j=1; j<=K;j++)
                {
                    if (current == 0)
                    {
                        dpt1[i][j] += dpt1[i - 1][j];
                        dpt2[i][j] += dpt2[i - 1][j];
                        dpt1[i][j] += dpt1[i - 1][j - 1] * 9;

                    }
                    else
                    {

                        dpt1[i][j] += dpt1[i - 1][j];
                        dpt2[i][j] += dpt2[i - 1][j - 1];
                        dpt1[i][j] += dpt1[i - 1][j - 1] * 9;

                        dpt1[i][j] += dpt2[i - 1][j];
                        dpt1[i][j] += dpt2[i - 1][j - 1] * (current-1  );
                    }

                }
            }


            Console.WriteLine(dpt1[s.Length-1][K] + dpt2[s.Length-1][K]);
            Console.ReadLine();
  
        }

        static List<int> Readints()
        {
            return  Console.ReadLine().Split(' ').Select(x =>x.ToInt()).ToList();
        }
        static int Readint()
        {
            return Console.ReadLine().ToInt();
        }
        static void Read2int(out int a,out int b)
        {
            var ints = Readints();
            a = ints[0];
            b = ints[1];
        }    
        static int Max(int a,int b)
        {
            return a > b ? a : b;
        }
        



    }

    static  class extensions
    {
        public static int ToInt(this string s)
        {
            return int.Parse(s);
        }

        public static string LJoin<T>(this IEnumerable<T> list)
        {
            return string.Join(" ",list);
        }


    } 


}

Submission status: Runtime Error

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

def comb(n,k):
	if k==0: return 1
	if k==1: return n
	if k==2: return n*(n-1)//2
	return n*(n-1)*(n-3)//2 # b/c K<=3

def f(N,K):
	if N==0: return 0
	strN	= str(N)
	top		= int(strN[0])
	digit	= len(strN)

	if K==1: return top-1

	result  = comb(digit-1, K-1) * (9**(K-1)) * (top-1)
	result += f(N - top*(10**digit), K-1)
	return result


print(f(N,K))

Submission status: Runtime Error

Solution code:
n = input()
k = input()
nl = len(n)

dp = [[[0]*(k+1) for _ in range(2)]for _ in range(nl+1)]
#dp[i][j][k] i:上からの桁数、j:smaller flag、k:0以外の数字の個数
dp[0][0][0] = 1

for i in range(nl):
  for j in range(2):
    for l in range(k+1):
      c = int(n[i])
      if j == 1:
        dp[i+1][j][l] += dp[i][j][l]
        if l < k:
          dp[i+1][j][l+1] += dp[i][j][l]*9
      else:
        if c == 0:#0しか選べない上にsmallを確定できない
          dp[i+1][0][l] += dp[i][j][l]
        else:
          dp[i+1][1][l] += dp[i][j][l]#cより確実に小さい0を使う。small確定
          if l < k:
            dp[i+1][1][l+1] += dp[i][j][l]*(c-1) #c以下の数字を使えばsmall確定
            dp[i+1][0][l+1] += dp[i][j][l] #cを使ったらsmall確定できない
            
print(dp[nl][0][k]+dp[nl][1][k])

Submission status: Runtime Error

Solution code:
#from fractions import gcd
#mod = 10 ** 9 + 7
#N = int(input())
#a = list(map(int,input().split()))
#a,b,c = map(int,input().split())
#ans = [0] * N
#math.ceilで切り上げ
#dp = [[0] * 4 for i in range(3)] #2次元配列初期化
#dp = [[[0] * 2 for i in range(3)] for j in range(5)]

import math
import string

def intinput():
    return int(input())

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

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

N = str(intinput())
K = intinput()
s = len(str(N))
flag = 0
dp = [[[0] * 3 for i in range(5)] for j in range(150)]
dp[0][0][0] = 1
dp[1][1][1] += int(N[0])-1
dp[2][2][1] += int(N[1])-1
dp[3][3][1] += int(N[2])-1
for h in range(1,s+1):
    dp[h][0][0] = 0
    dp[h][0][1] = 1
    for i in range(1,4):
        dp[h][i][0] += dp[h-1][i-1][0]
        dp[h][i][1] +=  dp[h-1][i-1][1] * 9 + dp[h-1][i][0] + dp[h-1][i][1]

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

Submission status: Runtime Error

Solution code:
#from fractions import gcd
#mod = 10 ** 9 + 7
#N = int(input())
#a = list(map(int,input().split()))
#a,b,c = map(int,input().split())
#ans = [0] * N
#math.ceilで切り上げ
#dp = [[0] * 4 for i in range(3)] #2次元配列初期化
#dp = [[[0] * 2 for i in range(3)] for j in range(5)]

import math
import string

def intinput():
    return int(input())

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

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

N = str(intinput())
K = intinput()
s = len(str(N))
flag = 0
dp = [[[0] * 2 for i in range(4)] for j in range(150)]
dp[0][0][0] = 1
dp[1][1][1] += int(N[0])-1
dp[2][2][1] += int(N[1])-1
dp[3][3][1] += int(N[2])-1
for h in range(1,s+1):
    dp[h][0][0] = 0
    dp[h][0][1] = 1
    for i in range(1,4):
        dp[h][i][0] += dp[h-1][i-1][0]
        dp[h][i][1] +=  dp[h-1][i-1][1] * 9 + dp[h-1][i][0] + dp[h-1][i][1]

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

Submission status: Runtime Error

Solution code:
#from fractions import gcd
#mod = 10 ** 9 + 7
#N = int(input())
#a = list(map(int,input().split()))
#a,b,c = map(int,input().split())
#ans = [0] * N
#math.ceilで切り上げ
#dp = [[0] * 4 for i in range(3)] #2次元配列初期化
#dp = [[[0] * 2 for i in range(3)] for j in range(5)]

import math
import string

def intinput():
    return int(input())

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

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

N = str(intinput())
K = intinput()
s = len(str(N))
flag = 0
dp = [[[0] * 2 for i in range(4)] for j in range(s+1)]
dp[0][0][0] = 1
dp[1][1][1] += int(N[0])-1
dp[2][2][1] += int(N[1])-1
dp[3][3][1] += int(N[2])-1
for h in range(1,s+1):
    dp[h][0][0] = 0
    dp[h][0][1] = 1
    for i in range(1,4):
        dp[h][i][0] += dp[h-1][i-1][0]
        dp[h][i][1] +=  dp[h-1][i-1][1] * 9 + dp[h-1][i][0] + dp[h-1][i][1]

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

Submission status: Runtime Error

Solution code:
from functools import lru_cache
@lru_cache(None)
n=int(input())
k=int(input())
def cal(n,k):
  if n<10:
    if k==0: return 1
    if k==1: return n
    return 0
  q,r=divmod(n,10)
  ret=0
  if k>=1:
    ret+=cal(q,k-1)*r
    ret+=cal(q-1,k-1)*(9-r)
  ret+=cal(q,k)
  return ret

print(cal(n,k))

Submission status: Runtime Error

Solution code:
n = list(map(int, list(input())))
k = int(input())

# 上の桁からDP
# 大きさが微妙な場合は分ける
# dp[桁][0の個数]

def solve(n, k):
    if k == 0:
        return 1
    dp = [[0 for _ in range(k+1)] for _ in range(len(n))]
    dp[0][0] = 1
    dp[0][1] = n[0] - 1
    for i in range(len(n) - 1):
        for j in range(k + 1):
            if j == 0:
                dp[i+1][0] = dp[i][0]
            else:
                dp[i+1][j] = dp[i][j-1] * 9 + dp[i][j]
    # first non-0
    i = 1
    while i < len(n) and n[i] == 0:
        i += 1
    return dp[len(n) - 1][k] + solve(n[i:], k-1)

print(solve(n, k))

Submission status: Runtime Error

Solution code:
def oneNum(N):
    answer = 0

    while(N > 0):
        if(N >= 9):
            answer = answer + 9
        else:
            answer = answer + N
        
        N = N // 10

    return answer

def twoNum(N):
    answer = 0

    strN = str(N)
    topN = int(strN[0])
    lenN = len(strN)

    answer = answer + oneNum(int(strN[1:])) + (topN - 1) * oneNum(int('9' * (lenN - 1)))

    N = int('9' * (lenN - 1))

    while(N >= 10):
        N = N // 10
        answer = answer + 9 * oneNum(N)

    return answer

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

    answer = 0

    if(K == 1):
        answer = oneNum(N)

    elif(K == 2):
        answer = twoNum(N)

    else:
        strN = str(N)
        topN = int(strN[0])
        lenN = len(strN)

        answer = answer + twoNum(int(strN[1:])) + (topN - 1) * twoNum(int('9' * (lenN - 1)))

        N = int('9' * (lenN - 1))

        while(N >= 100):
            N = N // 10
            answer = answer + 9 * twoNum(N)

    print(answer)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

keta = len(n)

# dp0 = ヨユーなやつ, dp1 = ギリなやつ
dp0 = [[0 for j in range(keta+1)] for i in range(keta+1)]
dp1 = [[0 for j in range(keta+1)] for i in range(keta+1)]

dp1[0][0] = 1

for i in range(keta):
    for j in range(keta+1):
        # ギリギリのやつ(dp1)の処理
        if n[i] == '0': # i+1桁目が0の場合
            dp1[i+1][j] = dp1[i][j] # 真上からスライド
        else: # i+1桁目が1~9の場合
            if j < keta:
                dp1[i+1][j+1] = dp1[i][j] # 左上からスライド
        
        # ヨユーなやつ(dp0)の処理
        if n[i] == '0': # i+1桁目が0の場合
            # i桁目がヨユーな状態ではi+1桁目には何でも入れられる
            dp0[i+1][j] += dp0[i][j] # i+1桁目に0を入れた場合
            if j < keta:
                dp0[i+1][j+1] += dp0[i][j] * 9 # i+1桁目に1~9を入れた場合
            # i桁目までギリだったときの、i+1桁目のヨユーなやつのカウント
                # 何もない(ギリである0しか入れられないため)
        else: # i+1桁目が1~9の場合
            # i桁目がヨユーな状態ではi+1桁目には何でも入れられる
            dp0[i+1][j] += dp0[i][j] # i+1桁目に0を入れた場合
            if j < keta:
                dp0[i+1][j+1] += dp0[i][j] * 9 # i+1桁目に1~9を入れた場合
            # i桁目までギリだったときの、i+1桁目のヨユーなやつのカウント
            dp0[i+1][j] += dp1[i][j] # i+1桁目に0を入れた場合
            if j < keta:
                dp0[i+1][j+1] += dp1[i][j] * (ord(n[i])-ord('0')-1) # i+1桁目にrange(1, n[i])を入れた場合

print(dp0[keta][k] + dp1[keta][k])

Submission status: Runtime Error

Solution code:
def digit_counter(number):
  count = 0
  while number > 0:
    a = number % 10
    if a != 0:
      count += 1
  	number //= 10
return count

num = int(input())
k = int(input())
for j in range(1, num):
	if digit_counter(j) == k:
  		count += 1
print(count)

Submission status: Runtime Error

Solution code:
def solve(n,k) :
    if n <= 9 and k == 1 :
        return n
    elif n <= 9 and k >= 2 :
        return 0
    else :
        m = n //10
        r = n % 10
        return  r * solve(m,k-1) + (9 - r) * solve(m-1,k-1) + solve(m,k)

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

Submission status: Runtime Error

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    S=ST()
    K=I()
    N=len(S)
    dp = [[[0]*2 for _ in range(N+1)]for _ in range(N+1)] #dp[i][count_not_zero][less]
    dp[0][0][0] = 1
    for i in range(N):
        for count_not_zero in range(min(N,4)):
            for less in range(2):
                if less:
                    upper = 10
                else:
                    upper = int(S[i])+1
                for j in range(upper):
                    dp[i+1][count_not_zero + (j!=0)][less | (j<int(S[i]))] += dp[i][count_not_zero][less]
    print(sum(dp[-1][K]))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    S=ST()
    K=I()
    N=len(S)
    dp = [[[0]*2 for _ in range(N+1)]for _ in range(N+1)] #dp[i][count_not_zero][less]
    dp[0][0][0] = 1
    for i in range(N):
        for count_not_zero in range(4):
            for less in range(2):
                if less:
                    upper = 10
                else:
                    upper = int(S[i])+1
                for j in range(upper):
                    dp[i+1][count_not_zero + (j!=0)][less | (j<int(S[i]))] += dp[i][count_not_zero][less]
    print(sum(dp[-1][K]))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import math

def combinations(n, r):
    if n < 0 or n < r:
        return 0
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))

def main():
    n = input().rstrip()
    k = int(input())
    if k == 1:
        print((int(n[0]) - 1) + 9 * (len(n) -  1) + 1)
    elif k == 2:
        a = (int(n[0]) - 1) * 9 * (len(n) - 1) + int(combinations(len(n) - 1, 2) * 9*9)
        b = int(n[1]) + 9 * (len(n)-2)
        print(a + b)
    elif k == 3:
        a = (int(n[1]) - 1) * 9 * (len(n) - 2) + int(combinations(len(n)-2, 2) * 9*9) + (int(n[2]) + 9*(len(n) - 3))
        b = (int(n[0]) - 1) * int(combinations(len(n)-1, 2) * 9*9)
        c = int(combinations(len(n)-1, 3) * 9*9*9)
        print(a+b+c)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import math

def combinations(n, r):
    if(n < r):
        return 0
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))

def main():
    n = input().rstrip()
    k = int(input())
    if k == 1:
        print((int(n[0]) - 1) + 9 * (len(n) -  1) + 1)
    elif k == 2:
        a = (int(n[0]) - 1) * 9 * (len(n) - 1) + int(combinations(len(n) - 1, 2) * 9*9)
        b = int(n[1]) + 9 * (len(n)-2)
        print(a + b)
    elif k == 3:
        a = (int(n[1]) - 1) * 9 * (len(n) - 2) + int(combinations(len(n)-2, 2) * 9*9) + (int(n[2]) + 9*(len(n) - 3))
        b = (int(n[0]) - 1) * int(combinations(len(n)-1, 2) * 9*9)
        c = int(combinations(len(n)-1, 3) * 9*9*9)
        print(a+b+c)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from scipy.special import comb

def main():
    n = input().rstrip()
    k = int(input())
    if k == 1:
        print((int(n[0]) - 1) + 9 * (len(n) -  1) + 1)
    elif k == 2:
        a = (int(n[0]) - 1) * 9 * (len(n) - 1) + int(comb(len(n) - 1, 2) * 9*9)
        b = int(n[1]) + 9 * (len(n)-2)
        print(a + b)
    elif k == 3:
        a = (int(n[1]) - 1) * 9 * (len(n) - 2) + int(comb(len(n)-2, 2) * 9*9) + (int(n[2]) + 9*(len(n) - 3))
        b = (int(n[0]) - 1) * int(comb(len(n)-1, 2) * 9*9)
        c = int(comb(len(n)-1, 3) * 9*9*9)
        print(a+b+c)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math
def check1(N):
    n = int(math.log10(N))
    return 9*n+(N//(10**n))
def check2(N):
    n = int(math.log10(N))
    return n*(n-1)/2*81+(N//(10**n)-1)*n*9+check1(N%(10**n))
def check3(N):
    n = int(math.log10(N))
    summ = 0
    if n >= 3:
        for i in range(2, n):
            summ += i*(i-1)/2
    return summ*729+(N//(10**n)-1)*n*(n-1)/2*81+check2(N%(10**n))
def main():
    N = int(input())
    K = int(input())
    if K == 1:
        print(int(check1(N)))
    elif K == 2:
        print(int(check2(N)))
    elif K == 3:
        print(int(check3(N)))
        
main()

Submission status: Runtime Error

Solution code:
import math
def check1(N):
    n = int(math.log10(N))
    return 9*n+(N//(10**n))
def check2(N):
    n = int(math.log10(N))
    return n*(n-1)/2*81+(N//(10**n)-1)*n*9+check1(N%(10**n))
def check3(N):
    n = int(math.log10(N))
    summ = 0
    for i in range(n):
        summ += i*(i-1)/2
    return summ*729+(N//(10**n)-1)*n*(n-1)/2*81+check2(N%(10**n))
def main():
    N = int(input())
    K = int(input())
    if K == 1:
        print(int(check1(N)))
    elif K == 2:
        print(int(check2(N)))
    elif K == 3:
        print(int(check3(N)))        
main()

Submission status: Runtime Error

Solution code:
import math
def check1(N):
    n = int(math.log10(N))
    return 9*n+(N//(10**n))
def check2(N):
    n = int(math.log10(N))
    return n*(n-1)/2*81+(N//(10**n)-1)*n*9+check1(N%(10**n))
def check3(N):
    n = int(math.log10(N))
    summ = 0
    for i in range(2, n):
        summ += i*(i-1)/2
    return summ*729+(N//(10**n)-1)*n*(n-1)/2*81+check2(N%(10**n))

def main():
    N = int(input())
    K = int(input())
    if K == 1:
        print(int(check1(N)))
    elif K == 2:
        print(int(check2(N)))
    elif K == 3:
        print(int(check3(N)))
        
main()

Submission status: Runtime Error

Solution code:
    r = 1
    for i in range(a):
        r *= i+1
    return r

def combinations(a, b):
    if a>=0 and b>=0 and a >= b:
        return pow(9, b) * factorial(a) // factorial(b) // factorial(a-b)
    else:
        return 0

def count(m, a, b):
    # return the count of numbers in range [0, m x 10^a] with b non zero digitals
    ## the count of numbers in range [0, m x 10^a) with b non zero digitals
    r = combinations(a-1, b) + (m-1) * combinations(a-1, b-1)
    if b == 1:
        ## m x 10^a
        r += 1
    return r

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

digit = list(map(int, str(N)))
M = len(digit)

C = 0
if M >= K:
    for i in range(K):
        C += count(digit[i], M-i, K-i)

print(C)

Submission status: Runtime Error

Solution code:
def factorial(a):
    r = 1
    for i in range(a):
        r *= i+1
    return r

def combinations(a, b):
    if a>=0 and b>=0 and a >= b:
        return pow(9, b) * factorial(a) // factorial(b) // factorial(a-b)
    else:
        return 0

def count(m, a, b):
    # return the count of numbers in range [0, m x 10^a] with b non zero digitals
    ## the count of numbers in range [0, m x 10^a) with b non zero digitals
    r = combinations(a-1, b) + (m-1) * combinations(a-1, b-1)
    if b == 1:
        ## m x 10^a
        r += 1
    return r

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

digit = list(map(int, str(N)))
M = len(digit)

C = 0
for i in range(K):
    C += count(digit[i], M-i, K-i)

print(C)

Submission status: Runtime Error

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

d=len(str(N)) #桁数
a=int(str(N)[0]) #最上位桁の数
if K==1:
  l=9*(d-1)
  m=a-1
  n=1
  print(int(l+m+n))
  
if K==2:
  if d==1:
    print(0)
  else:
    l=9**2*(d-1)*(d-2)/2 #最上位0
    m=(a-1)*9*(d-1) #最上位1~a-1 
    for i in range(1,d):
      if int(str(N)[i])!=0:
        n=(int(str(N)[i]))+9*(d-i-1)
        break
    print(int(l+m+n))
  
if K==3:
  if d<=2:
    print(0)
  else:
    l=9**3*(d-1)*(d-2)*(d-3)/6
    m=(a-1)*9**2*(d-1)*(d-2)/2
    for i in range(1,d):
      if int(str(N)[i])!=0:
        n=(int(str(N)[i]))*9*(d-i-1)+9**2*(d-i-1)*(d-i-2)/2
        break
    print(int(l+m+n))

Submission status: Runtime Error

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

d=len(str(N)) #桁数
a=int(str(N)[0]) #最上位桁の数
if K==1:
  l=9*(d-1)
  m=a-1
  n=1
  print(int(l+m+n))
  
if K==2:
  if d=1:
    print(0)
  else:
    l=9**2*(d-1)*(d-2)/2 #最上位0
    m=(a-1)*9*(d-1) #最上位1~a-1 
    for i in range(1,d):
      if int(str(N)[i])!=0:
        n=(int(str(N)[i]))+9*(d-i-1)
        break
    print(int(l+m+n))
  
if K==3:
  if d<=2:
    print(0)
  else:
    l=9**3*(d-1)*(d-2)*(d-3)/6
    m=(a-1)*9**2*(d-1)*(d-2)/2
    for i in range(1,d):
      if int(str(N)[i])!=0:
        n=(int(str(N)[i]))*9*(d-i-1)+9**2*(d-i-1)*(d-i-2)/2
        break
    print(int(l+m+n))

Submission status: Runtime Error

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

d=len(str(N)) #桁数
a=int(str(N)[0]) #最上位桁の数
if K==1:
  l=9*(d-1)
  m=a-1
  n=1
  print(int(l+m+n))
  
if K==2:
  l=9**2*(d-1)*(d-2)/2 #最上位0
  m=(a-1)*9*(d-1) #最上位1~a-1 
  for i in range(1,d):
    if int(str(N)[i])!=0:
      n=(int(str(N)[i]))+9*(d-i-1)
      break
  print(int(l+m+n))
  
if K==3:
  l=9**3*(d-1)*(d-2)*(d-3)/6
  m=(a-1)*9**2*(d-1)*(d-2)/2
  for i in range(1,d):
    if int(str(N)[i])!=0:
      n=(int(str(N)[i]))*9*(d-i-1)+9**2*(d-i-1)*(d-i-2)/2
      break
  print(int(l+m+n))

Submission status: Runtime Error

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

d=len(str(N)) #桁数
a=int(str(N)[0]) #最上位桁の数
if K==1:
  l=9*(d-1)
  m=a-1
  n=1
  print(l+m+n)
  
if K==2:
  l=9**2*(d-1)*(d-2)/2 #最上位0
  m=(a-1)*9*(d-1) #最上位1~a-1 
  for i in range(1,d):
    if int(str(N)[i])!=0:
      n=(int(str(N)[i]))+9*(d-i-1)
      break
  print(l+m+n)
  
if K==3:
  l=9**3*(d-1)*(d-2)*(d-3)/6
  m=(a-1)*9**2*(d-1)*(d-2)/2
  for i in range(1,d):
    if int(str(N)[i])!=0:
      n=(int(str(N)[i]))*9*(d-i-1)+9**2*(d-i-1)*(d-i-2)/2
      break
  print(l+m+n)

Submission status: Runtime Error

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

d=len(str(N)) #桁数
a=int(str(N)[0]) #最上位桁の数
if K==1:
  print(9*(d-1)+a)
  
if K==2:
  l=9**2*(d-1)*(d-2)/2 #最上位0
  m=(a-1)*9*(d-1) #最上位1~a-1 
  for i in range(1,d):
    if int(str(N)[i])!=0:
      n=(int(str(N)[i]))+9*(d-i-1)
      break
  print(l+m+n)
  
if K==3:
  l=9**3*(d-1)*(d-2)*(d-3)/6
  m=(a-1)*9**2*(d-1)*(d-2)/2
  for i in range(1,d):
    if int(str(N)[i])!=0:
      n=(int(str(N)[i]))*9*(d-i-1)+9**2*(d-i-1)*(d-i-2)/2
      break
  print(l+m+n)