Hướng dẫn giải của VOI 10 Bài 3 - Mã số thuế
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
const fi=''; maxl=13; type ar=array[1..maxl,-1..36] of int64; var n,q:int64; m,p,x,y,num,dg:longint; f,g,h:ar; a,b,c,e:array[1..40] of longint; d:array[1..10000] of longint; procedure calc(var f:ar;x:longint); var i,j:longint; begin for j:=0 to x-1 do f[1,j]:=1; for i:=2 to maxl do for j:=0 to x-1 do f[i,j]:=f[i-1,j]*x; end; procedure conv; var i:longint; nn:int64; begin nn:=n; while nn>0 do begin inc(dg); b[dg]:=nn mod 36; nn:=nn div 36; end; end; function check(i,x:longint):boolean; begin while i>0 do begin if i mod 36>=x then exit(false); i:=i div 36; end; check:=true; end; procedure wr(x:longint); var i,j:longint; begin j:=0; while x>0 do begin inc(j); e[j]:=x mod 36; x:=x div 36; end; for i:=j downto 1 do if e[i]<10 then write(e[i]) else write(chr(e[i]+87)); writeln; end; procedure vet; var i,j,sl:longint; begin sl:=0; for i:=1 to n do if check(i,x) and not check(i,y) then begin inc(sl); d[sl]:=i; end; if odd(p) then wr(d[q]) else wr(d[sl-q+1]); halt; end; procedure rf; var i,k,r:longint; begin read(n,m,p,q); k:=(m-1) shr 1; for i:=1 to k do read(c[i]); r:=(p+1) shr 1; if r>k then x:=36 else x:=c[r]; if r>1 then y:=c[r-1] else y:=0; if not odd(p) then conv; if n<=10000 then vet; end; procedure minus; var i,j:longint; s,t:boolean; oo:int64; begin s:=true; t:=true; oo:=100000000; oo:=oo*oo; for i:=1 to maxl do for j:=0 to x-1 do h[i,j]:=f[i,j]-g[i,j]; for i:=1 to maxl do for j:=0 to x-1 do begin if s then h[i,j]:=h[i,j-1]+h[i,j]; if h[i,j]>oo then s:=false; if t then f[i,j]:=f[i,j-1]+f[i,j]; if f[i,j]>oo then t:=false; end; end; procedure find; var i,j:longint; kt:boolean; res:int64; begin kt:=false; res:=0; for i:=dg downto 1 do begin if kt then begin if b[i]>=x then begin res:=res+f[i,x-1]; break; end; if i>1 then res:=res+f[i,b[i]-1] else res:=res+f[1,b[i]]; end else begin if b[i]>=x then begin res:=res+h[i,x-1]; break; end; if i>1 then res:=res+h[i,b[i]-1] else res:=res+h[1,b[i]]; if b[i]>=y then kt:=true; end; end; q:=res-q+1; end; procedure pr; var i,j:longint; kt,z:boolean; begin calc(f,x); if y>0 then calc(g,y); minus; if not odd(p) then find; if y=0 then begin inc(n); inc(q); end; for num:=1 to maxl do if h[num,x-1]>=n then break; kt:=false; for i:=num downto 1 do begin for j:=0 to x-1 do if kt then begin if f[i,j]>=q then begin a[i]:=j; q:=q-f[i,j-1]; break; end; end else begin if h[i,j]>=q then begin a[i]:=j; q:=q-h[i,j-1]; break; end; end; if j>=y then kt:=true; end; z:=false; for i:=num downto 1 do begin if not z and (a[i]=0) then continue; if a[i]>0 then z:=true; if a[i]<10 then write(a[i]) else write(chr(a[i]+87)); end; end; begin assign(input,fi); reset(input); rf; pr; close(input); end.
Code mẫu của happyboy99x
#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; }
Code mẫu của ladpro98
#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; }
Code mẫu của RR
#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; }
Code mẫu của ll931110
#include <algorithm> #include <iostream> #include <string> #include <vector> using namespace std; vector<int> c; long long pw[40][60]; long long n,q; int m,p; char a[36]; long long calc(long long x,int base) { vector<long long> digit; while (1) { digit.push_back(x % 36); x /= 36; if (!x) break; } reverse(digit.begin(),digit.end()); int sz = digit.size(); for (int i = 0; i < sz; i++) if (digit[i] >= base) for (int j = i; j < sz; j++) digit[j] = base - 1; long long ans = 0; for (int i = 0; i < sz; i++) ans += 1LL * digit[i] * pw[base][sz - i - 1]; ans++; return ans; } long long ascending(int x) { long long low = 1,high = n,ans = -1; while (low <= high) { long long med = (low + high)/2; long long tmp = calc(med,c[x]) - calc(med,c[x - 1]); if (tmp >= q) { ans = med; high = med - 1; } else low = med + 1; } return ans; } long long descending(int x) { long long s1 = calc(n,c[x]),s2 = calc(n,c[x - 1]); long long low = 1,high = n,ans = -1; while (low <= high) { long long med = (low + high)/2; long long t1 = calc(med - 1,c[x]),t2 = calc(med - 1,c[x - 1]); long long tmp = (s1 - t1) - (s2 - t2); if (tmp >= q) { ans = med; low = med + 1; } else high = med - 1; } return ans; } int main() { // freopen("taxid.in","r",stdin); // freopen("taxid.ou","w",stdout); cin >> n >> m >> p >> q; c.push_back(1); for (int i = 0; i < (m - 1)/2; i++) { int x; scanf("%d", &x); c.push_back(x); } c.push_back(36); for (int i = 2; i <= 36; i++) { pw[i][0] = 1; for (int j = 1; pw[i][j - 1] <= n/i; j++) pw[i][j] = pw[i][j - 1] * i; } for (int i = 0; i < 10; i++) a[i] = i + '0'; for (int i = 10; i < 36; i++) a[i] = i - 10 + 'a'; long long ret = (p & 1) ? ascending( (p + 1)/2 ) : descending( (p + 1)/2 ); string fin; while (ret) { fin += a[ret % 36]; ret /= 36; } for (int i = fin.size() - 1; i >= 0; i--) printf("%c", fin[i]); printf("\n"); }
Bình luận