TAXID - VOI10 - Mã số thuế
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
int64 f[20][2][2];
int ndigit(int64 n) {
int res = 0;
while(n != 0) ++res, n /= 36;
return res;
}
char toChar(int p) {
return p < 10 ? p + '0' : p - 10 + 'a';
}
string find(int64 n, int x, int y, int64 pos, bool rev) {
int len = ndigit(n);
memset(f, 0, sizeof f);
f[len][1][0] = f[len][1][1] = 1;
int64 num = n;
vector<int> v;
for(int i = len-1; i >= 0; --i, v.push_back(num % 36), num /= 36)
for(int j = 0; j < 2; ++j)
for(int k = 0; k < 2; ++k)
for(int d = 0; d < (k == 0 ? min(num % 36 + 1, y+0LL) : y); ++d)
f[i][j][k] += f[i+1][j | (x <= d ? 1 : 0)][k | (d < num % 36 ? 1 : 0)];
reverse(v.begin(), v.end());
if(rev) pos = f[0][0][0] - pos; else --pos;
string res ("");
for(int i = 0, j = 0, k = 0; i < len; ++i)
for(int d = 0; d < (k == 0 ? v[i] + 1 : y); ++d) {
int64 t = f[i+1][j | (x <= d ? 1 : 0)][k | (d < v[i] ? 1 : 0)];
if(t > pos) {
if(res.empty() ? d != 0 : true) res += toChar(d);
j |= x <= d ? 1 : 0;
k |= d < v[i] ? 1 : 0;
break;
} else pos -= t;
}
return res;
}
int main() {
ios::sync_with_stdio(false);
int64 n, m, p, q; cin >> n >> m >> p >> q;
vector<int> c;
for(int i = 0; i < (m-1)/2; ++i)
c.push_back(0), cin >> c.back();
cout << find(n, (p-1)/2-1 >= 0 ? c[(p-1)/2-1] : 1, (p-1)/2 < (m-1)/2 ? c[(p-1)/2] : 36, q, p % 2 == 0) << endl;
return 0;
}