結果

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

---

テストケース

ソースコード

#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_map>
#include<list>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
#define MK make_pair
const ll E=1e18+7;
const ll MOD=1000000007;

vector<vector<ll>> C;

vector<vector<ll>> mk_c(){
    ll mx=2500;
    vector<vector<ll>> c(mx+1,vector<ll>(mx+1,0));
    c[0][0]=1;
    for(ll i=0;i<mx;i++){
        for(ll t=0;t<mx;t++){
            for(int h=0;h<10;h++){
                if(t+h>mx){break;}
                c[i+1][t+h]+=c[i][t];
                if(c[i+1][t+h]>MOD){c[i+1][t+h]=MOD;}
            }
        }
    }
    return c;
}


int main(){
    C=mk_c();
    ll n,k;
    cin>>n>>k;
    string ans;
    for(int i=999;i>0;i--){
        for(int t=1;t<10;t++){
            ll count=C[i][n];
            if(count>=k){ans.push_back('0'+t-1); break;}
            k-=count;
            n--;
            if(t==9){ans.push_back('9');}
        }
    }
    ans.push_back(n+'0');
    bool f=false;
    for(int i=0;i<ans.size();i++){
        if(ans[i]!='0'){f=true;}
        if(f){cout<<ans[i];}
    }
    cout<<endl;
    
    
    return 0;
}