結果

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

---

テストケース

ソースコード

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAX = (1LL<<30);
ll N,K;

ll add(ll a,ll b){
  if( a+b > MAX )return MAX;
  else return a+b;
}

ll mem[1005][1005];
ll dfs(ll x,ll sum){
  if( x == 1001 )return ( sum == N );
  if( mem[x][sum] != -1 )return mem[x][sum];
  ll res=0;
  for(int i=0;i<=9;i++){
    if( sum + i > 1000 )break;
    res=add(res, dfs(x+1, sum+i) );
  }
  return mem[x][sum]=res;
}

int main(){
  memset( mem, -1, sizeof(mem) );
  

  cin>>N>>K;

  string ans="";
  ll x=0;
  ll sum=0;
  
  ll k=K-1;
  
  while(x<1001){
    for(int i=0;i<=9;i++){
      k-= dfs(x+1,  sum+i );
      if( k < 0 ){
        k+= dfs(x+1, sum+i );
        sum+=i;
        if( !ans.empty() || i!=0)ans.push_back('0'+i);
        break;
      }
    }
    x++;    
  }
  
  cout<< ans<<endl;
  return 0;
}