TAXID - VOI10 - Mã số thuế

Tác giả: ladpro98

Ngôn ngữ: C++

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <utility>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), a.end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int MAXN = 20;

using namespace std;
LL N;
int m, p, k;
LL q;
int c[100];

LL DP(LL n, int lim) {
    int digit[MAXN];
    int d = 0;
    while (n) {
        digit[++d] = n % 36;
        n /= 36;
    }
    reverse(digit + 1, digit + 1 + d);
    LL F[MAXN][2];
    F[0][0] = 0; F[0][1] = 1;
    FOR(i, 0, d) {
        if (digit[i + 1] < lim)
            F[i + 1][1] = F[i][1];
        else
            F[i + 1][1] = 0;
        F[i + 1][0] = F[i][1] * min(lim, digit[i + 1]) + F[i][0] * lim;
    }
    return F[d][0] + F[d][1];
}

LL cal(LL kth, int l, int r) {
    LL ll = 1, rr = N, ans;
    while (ll <= rr) {
        LL mid = ll + rr >> 1;
        LL sz = DP(mid, r) - DP(mid, l);
        if (sz >= kth) {
            ans = mid; rr = mid - 1;
        }
        else
            ll = mid + 1;
    }
    return ans;
}

char toHex(int x) {
    if (x <= 9) return '0' + x;
    return 'a' + (x - 10);
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> N >> m >> p >> q;
    k = (m - 1) / 2;
    REP(i, 1, k) cin >> c[i];
    c[0] = 1; c[++k] = 36;
    int low = c[(p + 1) / 2 - 1];
    int high = c[(p + 1) / 2];
    LL total = DP(N, high) - DP(N, low);
    LL res;
    if (p & 1) res = cal(q, low, high);
    else res = cal(total - q + 1, low, high);
    vector<int> digit;
    while (res) {digit.PB(res % 36); res /= 36;}
    REPD(i, SZ(digit) - 1, 0) cout << toHex(digit[i]);
    return 0;
}

Download