Editorial for VOI 10 Bài 3 - Mã số thuế


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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

Comments

Please read the guidelines before commenting.


There are no comments at the moment.