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