結果

提出番号 2143
提出者 minus9d
言語 C++
提出日時 2018-08-04 18:47:19
問題名 (72)K-th DigitSum
結果 AC
点数 100%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 AC 100% 4ms 8400KB
2 AC 100% 3ms 8304KB
3 AC 100% 2ms 8624KB
4 AC 100% 2ms 7776KB
5 AC 100% 4ms 8592KB
6 AC 100% 4ms 8784KB
7 AC 100% 4ms 8528KB
8 AC 100% 2ms 8080KB
9 AC 100% 4ms 8960KB
10 AC 100% 4ms 8832KB
11 AC 100% 2ms 8432KB
12 AC 100% 2ms 8176KB
13 AC 100% 2ms 8400KB
14 AC 100% 3ms 8688KB
15 AC 100% 4ms 8544KB
16 AC 100% 3ms 8400KB
17 AC 100% 4ms 8704KB
18 AC 100% 4ms 8656KB
19 AC 100% 2ms 7616KB
20 AC 100% 4ms 8368KB
21 AC 100% 3ms 8144KB
22 AC 100% 2ms 7536KB
23 AC 100% 3ms 7616KB
24 AC 100% 2ms 8032KB
25 AC 100% 2ms 8384KB
26 AC 100% 2ms 8416KB
27 AC 100% 4ms 8464KB
28 AC 100% 4ms 8784KB
29 AC 100% 2ms 7968KB
30 AC 100% 4ms 8992KB
31 AC 100% 5ms 9424KB
32 AC 100% 3ms 8368KB
33 AC 100% 3ms 8416KB
34 AC 100% 3ms 8432KB
35 AC 100% 3ms 7616KB
36 AC 100% 4ms 9184KB
37 AC 100% 4ms 8880KB
38 AC 100% 2ms 7504KB
39 AC 100% 4ms 8864KB
40 AC 100% 4ms 8576KB
41 AC 100% 2ms 8192KB
42 AC 100% 3ms 7968KB
43 AC 100% 2ms 7952KB
44 AC 100% 2ms 8400KB
45 AC 100% 3ms 8656KB
46 AC 100% 3ms 8432KB
47 AC 100% 2ms 7632KB
48 AC 100% 2ms 7888KB
49 AC 100% 3ms 8688KB
50 AC 100% 2ms 8240KB
51 AC 100% 2ms 8672KB

ソースコード

// URL: https://kotamanegi.com/Problems/view/?page=72
// 問題: 桁和がNとなる数の中でK番目に小さい数を求める
// 参考: https://kotamanegi.com/Submission/view/index.php?SubmissionID=1755

#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>


using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple


int N, K;
#define CMAX 1010
ll memo[CMAX][CMAX];
int vis[CMAX][CMAX];
ll cmb(int d, int sm) {
    if (d < 0 or sm < 0) return 0;
    if (d == 0) {
        if (sm == 0) return 1;
        else return 0;
    }
    if (vis[d][sm]) return memo[d][sm];

    ll res = 0;
    REP(i, 10) res += cmb(d - 1, sm - i);
    vis[d][sm] = 1;
    return memo[d][sm] = res;
}
void phase2(int d, int n) {
    printf("%d", n); N -= n;
    for(int dd = d - 1; dd >= 2; --dd) REP(nn, 10) {
        ll cnt = cmb(dd - 1, N - nn);
        if (cnt <= K) K -= cnt;
        else {
            printf("%d", nn);
            N -= nn;
            break;
        }
    }
    if(1 < d) printf("%d\n", N);
    else printf("\n");
}

int main() {
    cin >> N >> K;
    K--;

    FOR(d, 1, 1010) FOR(n, 1, 10) {
        ll cnt = cmb(d - 1, N - n);
        if (cnt <= K) K -= cnt;
        else {
            phase2(d, n);
            return 0;
        }
    }
}