TAXID - VOI10 - Mã số thuế

Tác giả: RR

Ngôn ngữ: C++

#include <iostream>
#include <algorithm>

#define FOR(i,a,b) for(long i=a; i<=b; i++)
#define DOWN(i,a,b) for(long i=a; i>=b; i--)
#define ll long long
using namespace std;

ll n,q;
long m,p,ct,cd;
long cs[20],c[40];
ll f[20][40][2][2];

void inp() {
    cin >>n >>m >>p >>q;
    FOR(i,1,(m-1)/2) cin >>c[i];
    c[0]=1;
    c[(m-1)/2+1]=36;
}

void update(long i,long last,long ok,long lower,long next,long lower2) {
    long ok2=ok;
    if (next>=cd) ok2=1;
    f[i+1][next][ok2][lower2]+=f[i][last][ok][lower];
}

ll get(ll n) {
    ll save=n;
    cs[0]=0;
    while (n) {
        cs[0]++;
        n/=36;
    }
    n=save; long now=cs[0];
    while (n) {
        cs[now]=n%36;
        n/=36;
        now--;
    }
    
    memset(f,0,sizeof f);
    f[0][0][0][0]=1LL;
    ct=c[(p+1)/2]-1;
    cd=c[(p+1)/2-1];
    
    FOR(i,0,cs[0]-1)
    FOR(last,0,ct)
    FOR(ok,0,1) {
        FOR(next,0,ct)
            update(i,last,ok,1,next,1);
            
        FOR(next,0,min(ct,cs[i+1]-1))
            update(i,last,ok,0,next,1);
        
        if (cs[i+1]<=ct)
            update(i,last,ok,0,cs[i+1],0);
    }
    
    ll res=0LL;
    FOR(last,0,ct)
        res+=f[cs[0]][last][1][1];
    return res;
}

void print(ll res) {
    if (!res) return ;
    print(res/36);
    long u=res%36;
    if (u<10) printf("%ld",u);
    else printf("%c",(char)('a'+u-10));
}

void solve() {
    if (p%2==0)
        q=1+get(n+1)-q;
    
    ll l=0LL, r=n, res=n;
    while (l<=r) {
        ll mid=(l+r)/2;
        if (get(mid+1)>=q) {
            res=mid;
            r=mid-1;
        } else l=mid+1;
    }
    print(res);
}

int main() {
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    inp();
    solve();
    return 0;
}

Download