Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
k = int(input())
if k == 1:
  flag = True
  cnt = 0
  while flag:
    for i in range(101):
      for j in range(1,10):
        if j*(10**i) <= n:
          cnt += 1
        else:
          flag = False
          break
elif k == 2:
  flag = True
  cnt = 0
  while flag:
    for i in range(1,101):
      for j in range(1,10):
        for l in range(i):
          for m in range(1,10):
            if j*(10**i)+m*(10**l) <= n:
              cnt += 1
            else:
              flag = False
              break
else:
  flag = True
  cnt = 0
  while flag:
    for i in range(2,25):
      for j in range(1,10):
        for l in range(1,i):
          for m in range(1,10):
            for o in range(l):
              for p in range(1,10):
                if j*(10**i)+m*(10**l)+p*(10**o) <= n:
                  cnt += 1
                else:
                  flag = False
                  break
print(cnt)

Fixed submission:
n = input()
k = int(input())
dp = [[[0,0,0,0],[0,0,0,0]] for i in range(len(n))] #dp[p][0][count]は、p桁目まではnより小さいことが確定している
#countは「0以外の桁」の登場回数、あくまで各桁に登場したt「以下」の数字かどうかを判定する。dp[p][1]は「〜と同じ」
dp[0][0][0] = 0
dp[0][0][1] = 1
dp[0][1][0] = 1
dp[0][1][1] = int(n[0])-1
for i in range(1,len(str(n))):
    if n[i] != '0':
        dp[i][0][0] = 0 #遷移前に同じで、遷移後に0でないものが0個かつ遷移前と同じ遷移はありえない
        dp[i][0][1] = dp[i-1][0][0] #ぴったりの数字(0でない)が入ればOK 下二つも同じ
        dp[i][0][2] = dp[i-1][0][1]
        dp[i][0][3] = dp[i-1][0][2]
        dp[i][1][0] = dp[i-1][1][0] #0を入れればOK
        dp[i][1][1] = dp[i-1][0][0]*(max(0,int(n[i])-1))+dp[i-1][0][1]+dp[i-1][1][1]+dp[i-1][1][0]*9
        dp[i][1][2] = dp[i-1][0][1]*(max(0,int(n[i])-1))+dp[i-1][0][2]+dp[i-1][1][2]+dp[i-1][1][1]*9
        dp[i][1][3] = dp[i-1][0][2]*(max(0,int(n[i])-1))+dp[i-1][0][3]+dp[i-1][1][3]+dp[i-1][1][2]*9
    else:
        dp[i][0][0] = dp[i-1][0][0]
        dp[i][0][1] = dp[i-1][0][1]
        dp[i][0][2] = dp[i-1][0][2]
        dp[i][0][3] = dp[i-1][0][3]
        dp[i][1][0] = dp[i-1][1][0] #0を入れればOK
        dp[i][1][1] = dp[i-1][1][0]*9+dp[i-1][1][1]
        dp[i][1][2] = dp[i-1][1][1]*9+dp[i-1][1][2]
        dp[i][1][3] = dp[i-1][1][2]*9+dp[i-1][1][3]
print(dp[len(n)-1][0][k]+dp[len(n)-1][1][k])

Buggy python submission (verdict: Runtime Error):
n = int(input())
k = int(input())
if k == 1:
  flag = True
  cnt = 0
  while flag:
    for i in range(101):
      for j in range(1,10):
        if j*(10**i) <= n:
          cnt += 1
        else:
          flag = False
          break
elif k == 2:
  flag = True
  cnt = 0
  while flag:
    for i in range(1,101):
      for j in range(1,10):
        for l in range(i):
          for m in range(1,10):
            if j*(10**i)+m*(10**l) <= n:
              cnt += 1
            else:
              flag = False
              break
else:
  print(0)
print(cnt)


Fixed submission:
n = input()
k = int(input())
dp = [[[0,0,0,0],[0,0,0,0]] for i in range(len(n))] #dp[p][0][count]は、p桁目まではnより小さいことが確定している
#countは「0以外の桁」の登場回数、あくまで各桁に登場したt「以下」の数字かどうかを判定する。dp[p][1]は「〜と同じ」
dp[0][0][0] = 0
dp[0][0][1] = 1
dp[0][1][0] = 1
dp[0][1][1] = int(n[0])-1
for i in range(1,len(str(n))):
    if n[i] != '0':
        dp[i][0][0] = 0 #遷移前に同じで、遷移後に0でないものが0個かつ遷移前と同じ遷移はありえない
        dp[i][0][1] = dp[i-1][0][0] #ぴったりの数字(0でない)が入ればOK 下二つも同じ
        dp[i][0][2] = dp[i-1][0][1]
        dp[i][0][3] = dp[i-1][0][2]
        dp[i][1][0] = dp[i-1][1][0] #0を入れればOK
        dp[i][1][1] = dp[i-1][0][0]*(max(0,int(n[i])-1))+dp[i-1][0][1]+dp[i-1][1][1]+dp[i-1][1][0]*9
        dp[i][1][2] = dp[i-1][0][1]*(max(0,int(n[i])-1))+dp[i-1][0][2]+dp[i-1][1][2]+dp[i-1][1][1]*9
        dp[i][1][3] = dp[i-1][0][2]*(max(0,int(n[i])-1))+dp[i-1][0][3]+dp[i-1][1][3]+dp[i-1][1][2]*9
    else:
        dp[i][0][0] = dp[i-1][0][0]
        dp[i][0][1] = dp[i-1][0][1]
        dp[i][0][2] = dp[i-1][0][2]
        dp[i][0][3] = dp[i-1][0][3]
        dp[i][1][0] = dp[i-1][1][0] #0を入れればOK
        dp[i][1][1] = dp[i-1][1][0]*9+dp[i-1][1][1]
        dp[i][1][2] = dp[i-1][1][1]*9+dp[i-1][1][2]
        dp[i][1][3] = dp[i-1][1][2]*9+dp[i-1][1][3]
print(dp[len(n)-1][0][k]+dp[len(n)-1][1][k])

Buggy python submission (verdict: Runtime Error):
n = int(input())
k = int(input())
if k == 1:
  flag = True
  cnt = 0
  while flag:
    for i in range(101):
      for j in range(1,10):
        if j*(10**i) <= n:
          cnt += 1
        else:
          flag = False
          break
elif k == 2:
  flag = True
  cnt = 0
  while flag:
    for i in range(1,101):
      for j in range(1,10):
        for l in range(i):
          for m in range(1,10):
            if j*(10**i)+m*(10**l) <= n:
              cnt += 1
            else:
              flag = False
              break
else:
  
print(cnt)

Fixed submission:
n = input()
k = int(input())
dp = [[[0,0,0,0],[0,0,0,0]] for i in range(len(n))] #dp[p][0][count]は、p桁目まではnより小さいことが確定している
#countは「0以外の桁」の登場回数、あくまで各桁に登場したt「以下」の数字かどうかを判定する。dp[p][1]は「〜と同じ」
dp[0][0][0] = 0
dp[0][0][1] = 1
dp[0][1][0] = 1
dp[0][1][1] = int(n[0])-1
for i in range(1,len(str(n))):
    if n[i] != '0':
        dp[i][0][0] = 0 #遷移前に同じで、遷移後に0でないものが0個かつ遷移前と同じ遷移はありえない
        dp[i][0][1] = dp[i-1][0][0] #ぴったりの数字(0でない)が入ればOK 下二つも同じ
        dp[i][0][2] = dp[i-1][0][1]
        dp[i][0][3] = dp[i-1][0][2]
        dp[i][1][0] = dp[i-1][1][0] #0を入れればOK
        dp[i][1][1] = dp[i-1][0][0]*(max(0,int(n[i])-1))+dp[i-1][0][1]+dp[i-1][1][1]+dp[i-1][1][0]*9
        dp[i][1][2] = dp[i-1][0][1]*(max(0,int(n[i])-1))+dp[i-1][0][2]+dp[i-1][1][2]+dp[i-1][1][1]*9
        dp[i][1][3] = dp[i-1][0][2]*(max(0,int(n[i])-1))+dp[i-1][0][3]+dp[i-1][1][3]+dp[i-1][1][2]*9
    else:
        dp[i][0][0] = dp[i-1][0][0]
        dp[i][0][1] = dp[i-1][0][1]
        dp[i][0][2] = dp[i-1][0][2]
        dp[i][0][3] = dp[i-1][0][3]
        dp[i][1][0] = dp[i-1][1][0] #0を入れればOK
        dp[i][1][1] = dp[i-1][1][0]*9+dp[i-1][1][1]
        dp[i][1][2] = dp[i-1][1][1]*9+dp[i-1][1][2]
        dp[i][1][3] = dp[i-1][1][2]*9+dp[i-1][1][3]
print(dp[len(n)-1][0][k]+dp[len(n)-1][1][k])