ソースコード
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
class Main{
static void solve(){
int n = ni();
int k = ni();
long[][] dp = new long[1001][n+1];
dp[0][0]=1;
StringBuilder ans = new StringBuilder();
int index=0;
for(int i=0;i<1000;++i){
for(int j=0;j<=n;++j){
for(int m=Math.max(0, j-9);m<=j;++m)dp[i+1][j]+=dp[i][m];
}
if(dp[i+1][n]>=k){
index=i+1;break;
}
}
for(int i=index;i>0;--i){
int size = ans.length();
long sum = 0;
for(int j=0;j<=Math.min(9, n);++j){
if(i==0){
// ans.append(n);
break;
}else{
if(sum + dp[i-1][n-j]>=k){
ans.append(j);
k-=sum;
n-=j;
break;
}
sum += dp[i-1][n-j];
}
}
if(size == ans.length())ans.append(0);
}
out.println(ans.toString());
}
public static void main(String[] args){
solve();
out.flush();
}
private static InputStream in = System.in;
private static PrintWriter out = new PrintWriter(System.out);
private static final byte[] buffer = new byte[1<<15];
private static int ptr = 0;
private static int buflen = 0;
private static boolean hasNextByte(){
if(ptr<buflen)return true;
ptr = 0;
try{
buflen = in.read(buffer);
} catch (IOException e){
e.printStackTrace();
}
return buflen>0;
}
private static int readByte(){ if(hasNextByte()) return buffer[ptr++]; else return -1;}
private static boolean isSpaceChar(int c){ return !(33<=c && c<=126);}
private static int skip(){int res; while((res=readByte())!=-1 && isSpaceChar(res)); return res;}
private static double nd(){ return Double.parseDouble(ns()); }
private static char nc(){ return (char)skip(); }
private static String ns(){
StringBuilder sb = new StringBuilder();
for(int b=skip();!isSpaceChar(b);b=readByte())sb.append((char)b);
return sb.toString();
}
private static int[] nia(int n){
int[] res = new int[n];
for(int i=0;i<n;++i)res[i]=ni();
return res;
}
private static long[] nla(int n){
long[] res = new long[n];
for(int i=0;i<n;++i)res[i]=nl();
return res;
}
private static int ni(){
int res=0,b;
boolean minus=false;
while((b=readByte())!=-1 && !((b>='0'&&b<='9') || b=='-'));
if(b=='-'){
minus=true;
b=readByte();
}
for(;'0'<=b&&b<='9';b=readByte())res=res*10+(b-'0');
return minus ? -res:res;
}
private static long nl(){
long res=0,b;
boolean minus=false;
while((b=readByte())!=-1 && !((b>='0'&&b<='9') || b=='-'));
if(b=='-'){
minus=true;
b=readByte();
}
for(;'0'<=b&&b<='9';b=readByte())res=res*10+(b-'0');
return minus ? -res:res;
}
}