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;
}