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