提出番号 | 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;
}
}
}
```