ソースコード
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1e9 + 7;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class T>
istream& operator >> (istream& is, vector<T>& v)
{
for (auto &i : v) is >> i;
return is;
}
template<class T>
ostream& operator<<(ostream& os, vector<T>& v)
{
const string delimiter = "\n";
REP(i, v.size())
{
os << v[i];
if (i != v.size() - 1) os << delimiter;
}
return os;
}
/*--------------------template--------------------*/
int L = 1001;
string add(string &a, string &b)
{
string res(L, '0');
int f = 0;
REP(i, L)
{
int aa = a[L - i - 1] - '0', bb = b[L - i - 1] - '0';
int c = aa + bb + f;
res[L - i - 1] = c % 10 + '0';
f = c / 10;
}
return res;
}
//
//string mean(string &a, string &b)
//{
//
//}
//
//string remz(string &a)
//{
//
//}
ll INF = 1e10;
int n, k;
ll dp[1111][1111];
ll solve1(int p, int sum, int& keta)
{
if (p == keta) return sum == n;
if (sum > n) return 0;
if (dp[p][sum] >= 0) return dp[p][sum];
ll res = 0;
REP(i, 10)
{
res += solve1(p + 1, sum + i, keta);
}
chmin(res, INF);
return dp[p][sum] = res;
}
ll count1(int keta)
{
MS(dp, -1);
return solve1(0, 0, keta);
}
string solve2(int keta)
{
string res(keta, '.');
int sum = 0;
ll tmp = 0;
REP(i, keta)
{
int c;
for (c = 0; c < 10; ++c)
{
ll x = solve1(i + 1, sum + c, keta);
if (tmp + x >= k)
{
break;
}
tmp += x;
}
assert(c >= 0 && c <= 9);
sum += c;
res[i] = c + '0';
}
return res;
}
int main()
{
cin.sync_with_stdio(false); cout << fixed << setprecision(10);
cin >> n >> k;
int lb = 0, ub = 1001;
while (ub - lb > 1)
{
MS(dp, -1);
int mid = (lb + ub) / 2;
if (count1(mid) >= k) ub = mid;
else lb = mid;
}
MS(dp, -1);
cout << solve2(ub) << endl;
return 0;
}