ソースコード
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.Reader;
import java.io.InputStreamReader;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
MyInput in = new MyInput(inputStream);
PrintWriter out = new PrintWriter(outputStream);
TaskF solver = new TaskF();
solver.solve(1, in, out);
out.close();
}
static class TaskF {
long[][] dp = new long[1001][1001];
public void solve(int testNumber, MyInput in, PrintWriter out) {
int n = in.nextInt();
int k = in.nextInt();
for (long[] d : dp)
Arrays.fill(d, -1L);
long[][] dp2 = new long[1001][1001];
for (int i = 0; i < dp2.length; i++) {
for (int j = 0; j < dp2[i].length; j++) {
dp2[i][j] = (i > 0 ? dp2[i - 1][j] : 0) + rec(i, j);
}
}
char[] ans = new char[1000];
Arrays.fill(ans, '0');
for (int i = 999; i >= 0; i--) {
for (int j = 0; j < 10; j++) {
final long v = dp2[i][n - j];
if (v >= k || j == 9) {
ans[ans.length - 1 - i] = (char) (j + '0');
// if (j > 0) k -= dp2[i][n-(j-1)];
// dump(i, j, v, j>0?dp2[i][n-j+1]:0);
n -= j;
break;
}
k -= v;
}
}
// dump(k);
for (int i = 0; i < ans.length; i++) {
if (ans[i] != '0') {
out.println(new String(ans, i, ans.length - i));
break;
}
}
}
long rec(int rest, int sum) {
if (sum < 0 || rest < 0) return 0;
if (rest == 0) return sum == 0 ? 1 : 0;
if (dp[rest][sum] < 0) {
dp[rest][sum] = 0;
for (int i = 0; i < 10; i++) {
dp[rest][sum] += rec(rest - 1, sum - i);
}
// dp[rest][sum] += rec(rest - 1, sum);
dp[rest][sum] = Math.min(Integer.MAX_VALUE, dp[rest][sum]);
// if (dp[rest][sum][first] != Integer.MAX_VALUE) dump(rest, sum, first, dp[rest][sum][first]);
}
return dp[rest][sum];
}
}
static class MyInput {
private final BufferedReader in;
private static int pos;
private static int readLen;
private static final char[] buffer = new char[1024 * 8];
private static char[] str = new char[500 * 8 * 2];
private static boolean[] isDigit = new boolean[256];
private static boolean[] isSpace = new boolean[256];
private static boolean[] isLineSep = new boolean[256];
static {
for (int i = 0; i < 10; i++) {
isDigit['0' + i] = true;
}
isDigit['-'] = true;
isSpace[' '] = isSpace['\r'] = isSpace['\n'] = isSpace['\t'] = true;
isLineSep['\r'] = isLineSep['\n'] = true;
}
public MyInput(InputStream is) {
in = new BufferedReader(new InputStreamReader(is));
}
public int read() {
if (pos >= readLen) {
pos = 0;
try {
readLen = in.read(buffer);
} catch (IOException e) {
throw new RuntimeException();
}
if (readLen <= 0) {
throw new MyInput.EndOfFileRuntimeException();
}
}
return buffer[pos++];
}
public int nextInt() {
int len = 0;
str[len++] = nextChar();
len = reads(len, isSpace);
int i = 0;
int ret = 0;
if (str[0] == '-') {
i = 1;
}
for (; i < len; i++) ret = ret * 10 + str[i] - '0';
if (str[0] == '-') {
ret = -ret;
}
return ret;
}
public char nextChar() {
while (true) {
final int c = read();
if (!isSpace[c]) {
return (char) c;
}
}
}
int reads(int len, boolean[] accept) {
try {
while (true) {
final int c = read();
if (accept[c]) {
break;
}
if (str.length == len) {
char[] rep = new char[str.length * 3 / 2];
System.arraycopy(str, 0, rep, 0, str.length);
str = rep;
}
str[len++] = (char) c;
}
} catch (MyInput.EndOfFileRuntimeException e) {
}
return len;
}
static class EndOfFileRuntimeException extends RuntimeException {
}
}
}