結果

提出番号	2388
提出者	kya
言語	C++
提出日時	2020-04-29 12:42:00
問題名	(72)K-th DigitSum
結果	WA
点数	0%

---

テストケース

ソースコード

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

constexpr int MAX = 1010;

vector<vector<long long>> make_table () {
    constexpr long long INF = 1e15;
    auto f = [&] (long long &x) { if (x > INF) x = INF; };
    vector<vector<long long>> dp(MAX, vector<long long>(MAX, 0));
    for (int i = 0; i < 10; i++) { dp[0][i] = 1; 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];
                    f(dp[i][j]);
                }
            }
        }
    }
    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 > 1; 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; }
            }
        }
        if (n > 9) while (true) { cout << endl; }
        if (1 < d) cout << n;
        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; }
        }
    }
}