結果

提出番号	1936
提出者	ats5515
言語	C++
提出日時	2018-08-04 14:39:01
問題名	(72)K-th DigitSum
結果	AC
点数	100%

---

テストケース

ソースコード

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
int dp[1001][1001];
int N, K;
int rec(int a, int b) {
	if (dp[a][b] != -1)return dp[a][b];
	if (a == 1000) {
		if (b == N) {
			dp[a][b] = 1;
		}
		else {
			dp[a][b] = 0;
		}
	}
	else {
		dp[a][b] = 0;
		for (int i = 0; i < 10; i++) {
			dp[a][b] += rec(a + 1, b + i);
		}
		if (dp[a][b] > K)dp[a][b] = K + 1;
	}
	return dp[a][b];
}
string res;
void rec2(int a, int b, int K2) {
	if (a == 1000) {
		//res.push_back((N - b) + '0');
		return;
	}
	for (int i = 0; i < 10; i++) {
		
		if (K2 - dp[a + 1][b + i] > 0) {
			K2 -= dp[a + 1][b + i];
		}
		else {
			res.push_back(i + '0');
			rec2(a + 1, b + i, K2);
			break;
		}
	}
}
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	cin >> N >> K;
	for (int i = 0; i <= 1000; i++) {
		for (int j = 0; j <= 1000; j++) {
			dp[i][j] = -1;
		}
	}
	rec(0, 0);
	/*cerr << dp[1000][0] << endl;
	cerr << dp[999][0] << endl;
	cerr << dp[998][0] << endl;*/
	rec2(0, 0, K);
	reverse(res.begin(), res.end());
	while (res.back() == '0')res.pop_back();
	reverse(res.begin(), res.end());
	cout << res << endl;
}