提出番号 | 2389 |
---|---|

提出者 | kya |

言語 | C++ |

提出日時 | 2020-04-29 18:05:55 |

問題名 | (72)K-th DigitSum |

結果 | AC |

点数 | 100% |

テストケース | 結果 | 得点 | 実行時間 | メモリ使用量 |
---|---|---|---|---|

1 | AC | 100% | 40ms | 35968KB |

2 | AC | 100% | 38ms | 35968KB |

3 | AC | 100% | 37ms | 35968KB |

4 | AC | 100% | 36ms | 35968KB |

5 | AC | 100% | 38ms | 35968KB |

6 | AC | 100% | 38ms | 35968KB |

7 | AC | 100% | 39ms | 35968KB |

8 | AC | 100% | 41ms | 35968KB |

9 | AC | 100% | 34ms | 35968KB |

10 | AC | 100% | 34ms | 35968KB |

11 | AC | 100% | 45ms | 35968KB |

12 | AC | 100% | 34ms | 35968KB |

13 | AC | 100% | 34ms | 35968KB |

14 | AC | 100% | 35ms | 35968KB |

15 | AC | 100% | 34ms | 35968KB |

16 | AC | 100% | 41ms | 35968KB |

17 | AC | 100% | 34ms | 35968KB |

18 | AC | 100% | 34ms | 35968KB |

19 | AC | 100% | 34ms | 35968KB |

20 | AC | 100% | 33ms | 35968KB |

21 | AC | 100% | 34ms | 35968KB |

22 | AC | 100% | 41ms | 35968KB |

23 | AC | 100% | 34ms | 35968KB |

24 | AC | 100% | 39ms | 35968KB |

25 | AC | 100% | 41ms | 35968KB |

26 | AC | 100% | 40ms | 35968KB |

27 | AC | 100% | 34ms | 35968KB |

28 | AC | 100% | 35ms | 35968KB |

29 | AC | 100% | 34ms | 35968KB |

30 | AC | 100% | 33ms | 35968KB |

31 | AC | 100% | 34ms | 35968KB |

32 | AC | 100% | 41ms | 35968KB |

33 | AC | 100% | 35ms | 35968KB |

34 | AC | 100% | 35ms | 35968KB |

35 | AC | 100% | 34ms | 35968KB |

36 | AC | 100% | 34ms | 35968KB |

37 | AC | 100% | 34ms | 35968KB |

38 | AC | 100% | 34ms | 35968KB |

39 | AC | 100% | 35ms | 35968KB |

40 | AC | 100% | 34ms | 35968KB |

41 | AC | 100% | 34ms | 35968KB |

42 | AC | 100% | 34ms | 35968KB |

43 | AC | 100% | 34ms | 35968KB |

44 | AC | 100% | 34ms | 35968KB |

45 | AC | 100% | 34ms | 35968KB |

46 | AC | 100% | 34ms | 35968KB |

47 | AC | 100% | 34ms | 35968KB |

48 | AC | 100% | 34ms | 35968KB |

49 | AC | 100% | 34ms | 35968KB |

50 | AC | 100% | 34ms | 35968KB |

51 | AC | 100% | 34ms | 35968KB |

```
#include <bits/stdc++.h>
using namespace std;
constexpr int MAX = 1010;
vector<vector<long long>> make_table () {
vector<vector<long long>> dp(MAX, vector<long long>(MAX, 0));
dp[0][0] = 1;
for (int i = 0; i < 10; i++) dp[1][i] = 1;
for (int i = 2; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
for (int d = 0; d < 10; d++) {
if (j - d >= 0) dp[i][j] += dp[i - 1][j - d];
}
}
}
return dp;
}
int main() {
int n;
long long k;
cin >> n >> k;
vector<vector<long long>> dp = make_table();
k--;
auto solve = [&] (int d, int x) {
cout << x; n -= x;
for (int i = d - 1; i > 1; i--) {
for (int j = 0; j < 10; j++) if (n - j >= 0) {
if (dp[i - 1][n - j] <= k) k -= dp[i - 1][n - j];
else { cout << j; n -= j; break; }
}
}
if (n > 9) while (true) { cout << endl; }
if (1 < d) cout << n;
cout << '\n';
};
for (int d = 1; d < MAX; d++) {
for (int x = 1; x < 10; x++) if (n - x >= 0) {
if (dp[d - 1][n - x] <= k) k -= dp[d - 1][n - x];
else { solve(d, x); return 0; }
}
}
}
```