結果

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

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 WA 0% 4ms 8288KB
2 WA 0% 3ms 8112KB
3 WA 0% 2ms 7536KB
4 WA 0% 2ms 7840KB
5 WA 0% 4ms 8576KB
6 WA 0% 4ms 8800KB
7 WA 0% 4ms 8528KB
8 WA 0% 2ms 8384KB
9 WA 0% 4ms 8960KB
10 WA 0% 4ms 8832KB
11 WA 0% 2ms 8192KB
12 WA 0% 2ms 8352KB
13 WA 0% 2ms 8416KB
14 WA 0% 3ms 7616KB
15 WA 0% 4ms 8528KB
16 WA 0% 3ms 8064KB
17 WA 0% 4ms 8704KB
18 WA 0% 4ms 8656KB
19 WA 0% 2ms 8192KB
20 WA 0% 4ms 8368KB
21 WA 0% 3ms 8160KB
22 WA 0% 2ms 7824KB
23 WA 0% 3ms 8096KB
24 WA 0% 2ms 8192KB
25 WA 0% 2ms 8432KB
26 WA 0% 2ms 8128KB
27 WA 0% 4ms 8448KB
28 WA 0% 4ms 8784KB
29 WA 0% 2ms 8144KB
30 WA 0% 4ms 9008KB
31 WA 0% 5ms 9424KB
32 WA 0% 3ms 7824KB
33 WA 0% 3ms 8400KB
34 WA 0% 3ms 7952KB
35 WA 0% 3ms 8432KB
36 WA 0% 4ms 9168KB
37 WA 0% 4ms 8880KB
38 WA 0% 2ms 7792KB
39 WA 0% 4ms 8864KB
40 WA 0% 4ms 8576KB
41 WA 0% 2ms 8416KB
42 WA 0% 3ms 7936KB
43 WA 0% 2ms 7968KB
44 WA 0% 2ms 8048KB
45 WA 0% 3ms 8688KB
46 WA 0% 3ms 7536KB
47 WA 0% 2ms 7840KB
48 WA 0% 2ms 8064KB
49 WA 0% 3ms 7824KB
50 WA 0% 2ms 7648KB
51 WA 0% 2ms 8096KB

ソースコード

// 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 >= 0; --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;
        }
    }
}