結果

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

---

テストケース

ソースコード

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>
#include <math.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<ll,ll> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
ll dp[1005][1005][10],n,k,q=0;
vector<int>ans;
int main(void){
    cin>>n>>k;
    dp[0][0][0]=1;
    for(int i=0;i<1000;i++,q++){
        if(dp[i][n][0]>k)break;
        for(int j=0;j<=n;j++){
            ll o=0;
            for(int s=0;s<10;s++)o+=dp[i][j][s];
            for(ll s=0;s<10;s++){
                dp[i+1][j+s][s]+=o;
            }
        }
    }
    for(int i=q;i>0;i--){
        ll s=0,p=0;
        for(;p<10;p++){
            s+=dp[i][n][p];
            if(s>=k){
                break;
            }
        }
        ans.PB(p);
        k-=(s-dp[i][n][p]);
        n-=p;
    }
    bool o=false;
    for(int i=0;i<ans.size();i++){
        if(ans[i]!=0){
            o=true;
            cout<<ans[i];
        }else{
            if(o)cout<<ans[i];
        }
    }
    cout<<endl;
}