結果

提出番号 2152
提出者 minus9d
言語 C++
提出日時 2018-08-05 10:40:25
問題名 (72)K-th DigitSum
結果 AC
点数 100%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 AC 100% 4ms 8272KB
2 AC 100% 3ms 8304KB
3 AC 100% 2ms 8432KB
4 AC 100% 2ms 7984KB
5 AC 100% 4ms 8608KB
6 AC 100% 4ms 8800KB
7 AC 100% 4ms 8544KB
8 AC 100% 2ms 8128KB
9 AC 100% 4ms 8976KB
10 AC 100% 4ms 8848KB
11 AC 100% 2ms 8432KB
12 AC 100% 2ms 8192KB
13 AC 100% 3ms 8400KB
14 AC 100% 3ms 7632KB
15 AC 100% 4ms 8560KB
16 AC 100% 3ms 7920KB
17 AC 100% 4ms 8736KB
18 AC 100% 4ms 8672KB
19 AC 100% 2ms 8720KB
20 AC 100% 4ms 8448KB
21 AC 100% 4ms 8704KB
22 AC 100% 2ms 8656KB
23 AC 100% 2ms 7760KB
24 AC 100% 2ms 8048KB
25 AC 100% 2ms 7600KB
26 AC 100% 2ms 8432KB
27 AC 100% 4ms 8464KB
28 AC 100% 4ms 8800KB
29 AC 100% 2ms 7648KB
30 AC 100% 4ms 9008KB
31 AC 100% 5ms 9424KB
32 AC 100% 3ms 7520KB
33 AC 100% 3ms 8032KB
34 AC 100% 3ms 8384KB
35 AC 100% 2ms 8256KB
36 AC 100% 4ms 9184KB
37 AC 100% 4ms 8896KB
38 AC 100% 2ms 8416KB
39 AC 100% 4ms 8896KB
40 AC 100% 4ms 8592KB
41 AC 100% 2ms 8400KB
42 AC 100% 3ms 8080KB
43 AC 100% 2ms 8432KB
44 AC 100% 2ms 8432KB
45 AC 100% 4ms 8560KB
46 AC 100% 3ms 8304KB
47 AC 100% 2ms 8384KB
48 AC 100% 2ms 7792KB
49 AC 100% 3ms 8640KB
50 AC 100% 2ms 8016KB
51 AC 100% 2ms 7744KB

ソースコード

// 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

#define CMAX 1010
ll memo[CMAX][CMAX];
int vis[CMAX][CMAX];

// 桁の数がd、各桁の合計がsmであるような場合の数を求める。
// ただし先頭が0になるのを許容する。
// 例: cmb(3, 2) は 002, 011, 020, 101, 110, 200なので6
ll cmb(int d, int sm) {
    if (d < 0 || 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;
}

// 桁数がちょうどd桁、かつ、最初がnである整数のうち、
// 全桁の合計がNで、かつ、K番目の整数を表示
void phase2(int d, int n, int N, int K) {
    // 最初の文字はnで確定
    printf("%d", n); N -= n;
    // 2文字目以降を上の桁から順に確定していく
    // nYXXX  のYの部分を決めたい場合、dd=4
    for(int dd = d - 1; dd >= 2; --dd) {
        // Yに何が入るかを0から順番に試す
        REP(nn, 10) {
            ll cnt = cmb(dd - 1, N - nn);
            if (cnt < K) K -= cnt;
            // Yに入る数字がnnで確定
            else {
                printf("%d", nn);
                N -= nn;
                break;
            }
        }
    }
    // 最後に残った数字が最後の桁
    if(1 < d) printf("%d\n", N);
    else printf("\n");
}

void solve(int N, int K) {
    // dは桁数
    FOR(d, 1, 1010) {
        // 例えばd=3のとき、"1xx", "2xx"と順にループ
        FOR(n, 1, 10) {
            // 上の"xx"の部分の桁和がN-nになる場合の数を計算
            ll cnt = cmb(d - 1, N - n);
            if (cnt < K) K -= cnt;
            else {
                // d桁で、phase2
                phase2(d, n, N, K);
                return;
            }
        }
    }
}


int main() {
    int N, K;
    cin >> N >> K;
    solve(N, K);
}