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

Download