結果

提出番号	2390
提出者	kya
言語	C++
提出日時	2020-04-29 18:09:46
問題名	(72)K-th DigitSum
結果	AC
点数	100%

---

テストケース

ソースコード

#include <bits/stdc++.h>
using namespace std;

constexpr int MAX = 1010;

vector<vector<long long>> make_table () {
    vector<vector<long long>> dp(MAX, vector<long long>(MAX, 0));
    dp[0][0] = 1;
    for (int i = 0; i < 10; i++) dp[1][i] = 1;
    for (int i = 2; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            for (int d = 0; d < 10; d++) {
                if (j - d >= 0) dp[i][j] += dp[i - 1][j - d];
            }
        }
    }
    return dp;
}

int main() {
    int n;
    long long k;
    cin >> n >> k;
    
    vector<vector<long long>> dp = make_table();
    
    k--;
    auto solve = [&] (int d, int x) {
        cout << x; n -= x;
        for (int i = d - 1; i > 0; i--) {
            for (int j = 0; j < 10; j++) if (n - j >= 0) {
                if (dp[i - 1][n - j] <= k) k -= dp[i - 1][n - j];
                else { cout << j; n -= j; break; }
            }
        }
        cout << '\n';
    };
    
    for (int d = 1; d < MAX; d++) {
        for (int x = 1; x < 10; x++) if (n - x >= 0) {
            if (dp[d - 1][n - x] <= k) k -= dp[d - 1][n - x];
            else { solve(d, x); return 0; }
        }
    }
}