提出 #11532810

---

ソースコード 拡げる

//Patwari26
#include<bits/stdc++.h>
using namespace std;

#define ll          long long
#define pb          push_back
#define endl        '\n'
#define mii         map<ll,ll>
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll)x.size()
#define hell        1000000007
#define INF         (1ll<<60)
#define rep(i,a,b)  for(ll i=a;i<=b;i++)
#define rrep(i,a,b)  for(ll i=a;i>=b;i--)
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define time        cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a * (b / gcd(a, b)); }
const int N=12;
ll m,n;
string s,t;
ll dp[12][N][2][2];
//code for all the nummbers divisible by m
ll digitdp(ll zero,ll last,ll idx,ll lt,ll rt){ // lt=0(fixed) lt=1(free)
    if(idx==n) return 1;
    if(dp[last][idx][lt][rt]!=-1) return dp[last][idx][lt][rt];
    ll &curr=dp[last][idx][lt][rt];
    curr=0;
    ll mi=0,mx=9;
    if(!lt) mi=s[idx]-'0';
    if(!rt) mx=t[idx]-'0';
    rep(i,mi,mx){
        ll nlt=(lt|(i>s[idx]-'0'));
        ll nrt=(rt|(i<t[idx]-'0'));
        if(idx>=1){
            if(abs(last-i)<=1 || (zero==idx)) {
               if(i!=0) curr=(curr+digitdp(zero,i,idx+1,nlt,nrt));
               else curr=(curr+digitdp(zero+1,i,idx+1,nlt,nrt));
            }
        }
        else {
            if(i!=0)
            curr=(curr+digitdp(zero,i,idx+1,nlt,nrt));
        else curr=(curr+digitdp(zero+1,i,idx+1,nlt,nrt));
        }
    }
    return curr;
}
ll check(ll num){
    s="";
    t="";
    while(num!=0){
        t.pb((char)(num%10+'0'));
        s.pb('0');
        num/=10;
    }
    reverse(all(t));
    // cout<<s<<" "<<t<<endl;
    n=sz(t);
    // cout<<n<<" ";
    memset(dp,-1,sizeof(dp));
    ll fin=digitdp(0,0,0,0,0);
    // cout<<fin<<endl;
    return fin-1;
}
void solve(){
    ll k;
    cin>>k;
    ll lo=1,hi=3234566667;
    ll ans=-1;
    while(lo<=hi){
        ll mid=(lo+hi)/2;
        // cout<<mid<<endl;
        if(check(mid)>=k){
            ans=mid;
            hi=mid-1;
        }
        else lo=mid+1;
    }
    // cout<<check(32)<<endl;
    cout<<ans;
}
signed main()
{
    ios
    int TESTS=1;
    //cin>>TESTS;
    while(TESTS--){
        solve();
    }
    time
    return 0;
}

提出情報

ジャッジ結果