結果

提出番号	1837
提出者	beet
言語	C++
提出日時	2018-08-04 14:09:53
問題名	(72)K-th DigitSum
結果	AC
点数	100%

---

テストケース

ソースコード

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

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
const Int INF = 1e12;
Int dp[1050][1050];
Int dp2[1050][1050];
signed main(){
  Int n,k;
  cin>>n>>k;
  memset(dp,0,sizeof(dp));
  for(Int i=1;i<10;i++) dp[1][i]=1;
  dp2[0][0]=1;
  for(Int i=0;i<=1010;i++){
    for(Int j=0;j<=1010;j++){
      for(Int k=0;k<10;k++){
	dp[i+1][j+k]+=dp[i][j];
	chmin(dp[i+1][j+k],INF);
	dp2[i+1][j+k]+=dp2[i][j];
	chmin(dp2[i+1][j+k],INF);
      }
    }
  }
  k--;
  Int l=0;
  while(dp[l][n]<=k) k-=dp[l++][n];

  //cout<<l<<endl;
  Int flg=1;
  while(l){
    Int x=flg;
    flg=0;
    while(dp2[l-1][n-x]<=k) k-=dp2[l-1][n-x++];
    cout<<x;
    n-=x;
    l--;
  }
  cout<<endl;
  return 0;
}