結果

提出番号 2147
提出者 shot
言語 C++
提出日時 2018-08-05 00:13:00
問題名 (72)K-th DigitSum
結果 AC
点数 100%

テストケース

テストケース 結果 得点 実行時間 メモリ使用量
1 AC 100% 18ms 35968KB
2 AC 100% 17ms 35968KB
3 AC 100% 17ms 35968KB
4 AC 100% 17ms 35968KB
5 AC 100% 18ms 35968KB
6 AC 100% 18ms 35968KB
7 AC 100% 18ms 35968KB
8 AC 100% 18ms 35968KB
9 AC 100% 16ms 35968KB
10 AC 100% 17ms 35968KB
11 AC 100% 18ms 35968KB
12 AC 100% 17ms 35968KB
13 AC 100% 16ms 35968KB
14 AC 100% 18ms 35968KB
15 AC 100% 18ms 35968KB
16 AC 100% 15ms 35968KB
17 AC 100% 15ms 35968KB
18 AC 100% 18ms 35968KB
19 AC 100% 16ms 35968KB
20 AC 100% 17ms 35968KB
21 AC 100% 18ms 35968KB
22 AC 100% 16ms 35968KB
23 AC 100% 18ms 35968KB
24 AC 100% 18ms 35968KB
25 AC 100% 18ms 35968KB
26 AC 100% 18ms 35968KB
27 AC 100% 18ms 35968KB
28 AC 100% 17ms 35968KB
29 AC 100% 18ms 35968KB
30 AC 100% 16ms 35968KB
31 AC 100% 18ms 35968KB
32 AC 100% 18ms 35968KB
33 AC 100% 18ms 35968KB
34 AC 100% 17ms 35968KB
35 AC 100% 17ms 35968KB
36 AC 100% 16ms 35968KB
37 AC 100% 17ms 35968KB
38 AC 100% 16ms 35968KB
39 AC 100% 17ms 35968KB
40 AC 100% 18ms 35968KB
41 AC 100% 18ms 35968KB
42 AC 100% 14ms 35968KB
43 AC 100% 17ms 35968KB
44 AC 100% 17ms 35968KB
45 AC 100% 16ms 35968KB
46 AC 100% 16ms 35968KB
47 AC 100% 18ms 35968KB
48 AC 100% 17ms 35968KB
49 AC 100% 18ms 35968KB
50 AC 100% 17ms 35968KB
51 AC 100% 18ms 35968KB

ソースコード

#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int N, K;
  cin >> N >> K; 

  vector<vector<int> > dp(1010, vector<int>(1010, 0));
  dp[0][0] = 1;
  for ( int i = 0; i < 1001; i++ ) {
    for ( int j = 0; j < 1001; j++ ) {
      for ( int k = 0; k < 10; k++ ) {
	if ( j+k > 1000 ) continue;	
	dp[i+1][j+k] += dp[i][j];	
      }
    }
  }

  int d = 0;
  while ( dp[d][N] <= K ) d++;
  bool flag = false;
  while ( d >= 1 ) {
    int i;
    int sum = 0;
    for ( i = 0; i < 10; i++ ) {
      if ( sum+dp[d-1][N-i] >= K ) break;
      sum += dp[d-1][N-i];           
    }
    if ( flag || i ) cout << i;
    flag = true;    
    K -= sum;    
    N -= i;    
    d--;
  }
  cout << endl;  
  
  return 0;
}