ソースコード
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;
static const ll INF = (ll)1e16;
ll dp[2][1005][1005];
ll solve(int top, int m, int N){
if(dp[top][m][N] != -1) return dp[top][m][N];
if(m==1){
if(0 <= N && N <= 9) return dp[top][m][N] = 1;
return dp[top][m][N] = 0;
}
if(top == 1){
ll ret = 0;
REP(i,1,10){
int n = N-i;
if(n < 0) continue;
ret += solve(0, m-1, n);
if(ret > INF) ret = INF;
}
return dp[top][m][N] = ret;
}else{
ll ret = 0;
rep(i,10){
int n = N-i;
if(n < 0) continue;
ret += solve(0, m-1, n);
if(ret > INF) ret = INF;
}
return dp[top][m][N] = ret;
}
}
string ans;
void solve2(int top, int m, int N, int cnt, string num = ""){
//cout << top << " " << m << " " << N << " " << cnt << " " << num << endl;
if(ans != "") return;
if(m==1){
if(cnt == 1){
if(0 <= N && N <= 9){
ans = num + (char)('0' + N);
return;
}
}else{
return;
}
}
if(top == 1){
ll ret = 0;
REP(i,1,10){
int n = N-i;
if(n < 0) continue;
if(ret + solve(0,m-1,n) < cnt){
ret += solve(0,m-1,n);
}else{
solve2(0, m-1, n, cnt-ret, num + (char)('0' + i));
return;
}
}
}else{
ll ret = 0;
rep(i,10){
int n = N-i;
if(n < 0) continue;
if(ret + solve(0,m-1,n) < cnt){
ret += solve(0,m-1,n);
}else{
solve2(0, m-1, n, cnt-ret, num + (char)('0' + i));
return;
}
}
}
}
int main(){
int N, K;
cin >> N >> K;
rep(i,2) rep(j,1005) rep(k,1005) dp[i][j][k] = -1;
int m = 0;
ll cnt = 0;
ll base = 0;
REP(i,1,1000){
ll ret = solve(1, i, N);
if(K <= base + ret){
m = i;
cnt = K - base;
break;
}
base += ret;
}
ans = "";
solve2(1, m, N, cnt);
cout << ans << endl;
return 0;
}