結果

提出番号 1755
提出者 hamayanhamayan
言語 C++
提出日時 2018-08-04 13:45:37
問題名 (72)K-th DigitSum
結果 AC
点数 100%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 AC 100% 3ms 8608KB
2 AC 100% 3ms 8176KB
3 AC 100% 2ms 8320KB
4 AC 100% 2ms 8400KB
5 AC 100% 4ms 8928KB
6 AC 100% 4ms 9136KB
7 AC 100% 4ms 8896KB
8 AC 100% 2ms 7808KB
9 AC 100% 4ms 9328KB
10 AC 100% 4ms 9200KB
11 AC 100% 2ms 8256KB
12 AC 100% 2ms 8432KB
13 AC 100% 3ms 8144KB
14 AC 100% 3ms 8000KB
15 AC 100% 3ms 8880KB
16 AC 100% 3ms 8704KB
17 AC 100% 4ms 9056KB
18 AC 100% 4ms 9008KB
19 AC 100% 2ms 8352KB
20 AC 100% 4ms 8720KB
21 AC 100% 3ms 8720KB
22 AC 100% 2ms 8176KB
23 AC 100% 3ms 8416KB
24 AC 100% 2ms 8192KB
25 AC 100% 2ms 8176KB
26 AC 100% 2ms 8144KB
27 AC 100% 3ms 8800KB
28 AC 100% 4ms 9136KB
29 AC 100% 2ms 8176KB
30 AC 100% 4ms 9360KB
31 AC 100% 5ms 9760KB
32 AC 100% 3ms 8000KB
33 AC 100% 3ms 7776KB
34 AC 100% 3ms 8720KB
35 AC 100% 4ms 7968KB
36 AC 100% 4ms 9520KB
37 AC 100% 4ms 9216KB
38 AC 100% 2ms 8416KB
39 AC 100% 4ms 9232KB
40 AC 100% 4ms 8944KB
41 AC 100% 2ms 7648KB
42 AC 100% 3ms 8416KB
43 AC 100% 2ms 8672KB
44 AC 100% 2ms 8720KB
45 AC 100% 4ms 8880KB
46 AC 100% 2ms 7648KB
47 AC 100% 2ms 7504KB
48 AC 100% 2ms 8432KB
49 AC 100% 3ms 8032KB
50 AC 100% 2ms 7904KB
51 AC 100% 2ms 7552KB

ソースコード

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
            ∧_∧  
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     
    /   \     | |     
    /   / ̄ ̄ ̄ ̄/  |  
  __(__ニつ/     _/ .| .|____  
     \/____/ (u ⊃  
---------------------------------------------------------------------------------------------------*/




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, 0, 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;
    rrep(dd, d - 1, 2) rep(nn, 0, 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");
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    K--;

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