結果

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

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 AC 100% 38ms 35968KB
2 AC 100% 38ms 35968KB
3 AC 100% 38ms 35968KB
4 AC 100% 39ms 35968KB
5 AC 100% 38ms 35968KB
6 AC 100% 40ms 35968KB
7 AC 100% 41ms 35968KB
8 AC 100% 38ms 35968KB
9 AC 100% 34ms 35968KB
10 AC 100% 41ms 35968KB
11 WA 0% 37ms 35968KB
12 AC 100% 34ms 35968KB
13 AC 100% 41ms 35968KB
14 AC 100% 33ms 35968KB
15 AC 100% 34ms 35968KB
16 AC 100% 34ms 35968KB
17 AC 100% 34ms 35968KB
18 AC 100% 33ms 35968KB
19 AC 100% 33ms 35968KB
20 AC 100% 34ms 35968KB
21 AC 100% 34ms 35968KB
22 AC 100% 41ms 35968KB
23 AC 100% 41ms 35968KB
24 AC 100% 34ms 35968KB
25 AC 100% 34ms 35968KB
26 AC 100% 34ms 35968KB
27 AC 100% 35ms 35968KB
28 AC 100% 33ms 35968KB
29 AC 100% 33ms 35968KB
30 AC 100% 34ms 35968KB
31 AC 100% 34ms 35968KB
32 AC 100% 34ms 35968KB
33 AC 100% 34ms 35968KB
34 AC 100% 33ms 35968KB
35 AC 100% 33ms 35968KB
36 AC 100% 33ms 35968KB
37 AC 100% 34ms 35968KB
38 AC 100% 34ms 35968KB
39 AC 100% 34ms 35968KB
40 AC 100% 34ms 35968KB
41 AC 100% 34ms 35968KB
42 AC 100% 33ms 35968KB
43 AC 100% 34ms 35968KB
44 AC 100% 34ms 35968KB
45 AC 100% 33ms 35968KB
46 AC 100% 33ms 35968KB
47 AC 100% 34ms 35968KB
48 AC 100% 34ms 35968KB
49 AC 100% 34ms 35968KB
50 AC 100% 34ms 35968KB
51 AC 100% 34ms 35968KB

ソースコード

#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));
    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];
            }
        }
    }
    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 (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; }
        }
    }
}