結果

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

テストケース

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

ソースコード

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

constexpr int MAX_N = 1010;
constexpr int MAX = 1010;

int main() {
    int n;
    long long k;
    cin >> n >> k;
    
    long long dp[MAX][MAX_N] = {};
    for (int i = 0; i < 10; i++) dp[1][i] = 1;
    for (int i = 2; i < MAX; i++) {
        for (int j = 0; j < MAX_N; j++) {
            for (int d = 0; d < 10; d++) {
                if (j - d >= 0) dp[i][j] += dp[i - 1][j - d];
            }
        }
    }
    
    int id = 0; // 答えの桁数
    while (dp[id][n] <= k) id++;
    
    vector<int> ans;
    for (int i = 1; i < 10; i++) if (n - i >= 0) {
        if (dp[id - 1][n - i] < k) k -= dp[id - 1][n - i];
        else { ans.emplace_back(i); n -= i; break; }
    }
    
    auto solve = [&] () -> void {
        for (int i = 0; i < 10; i++) if (n - i >= 0) {
            if (dp[id - 1][n - i] < k) k -= dp[id - 1][n - i];
            else { ans.emplace_back(i); n -= i; return; }
        }
    };
    
    while (id--) solve();
    
    for (const int &d : ans) cout << d; cout << '\n';
    
    return 0;
}