結果

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

---

テストケース

ソースコード

#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;
}