Editorial for VOI 08 Bài 3 - Quà tết


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='';
      fo='';
      base=1000000000;
      dg=9;
type bignum=array[0..100] of longint;
var n:longint;
    x,y:qword;
    z,h:bignum;
    p:array[0..41] of qword;

procedure rf;
begin
     read(n,x,y);
     y:=p[n]-1-y;
end;

procedure wf;
var i,j,t:longint; s:string;
begin
     for i:=z[0] downto 1 do
     begin
          if i<z[0] then
          begin
               str(z[i],s);
               t:=length(s);
               for j:=t+1 to dg do write(0);
          end;
          write(z[i]);
     end;
     write(' ');
end;

procedure plus(var h:bignum);
var i,mem:longint;
begin
     mem:=0;
     for i:=1 to h[0] do
     begin
          h[i]:=h[i] shl 1+mem;
          if h[i]>=base then
          begin
               mem:=1;
               h[i]:=h[i]-base;
          end
          else mem:=0;
     end;
     if mem>0 then
     begin
          inc(h[0]);
          h[h[0]]:=1;
     end;
end;

procedure minus(var a:bignum;b,c:bignum);
var i,mem:longint;
begin
     mem:=-1;
     for i:=1 to b[0] do
     begin
          a[i]:=b[i]-c[i]-mem;
          if a[i]<0 then
          begin
               a[i]:=a[i]+base;
               mem:=1;
          end
          else mem:=0;
     end;
     a[0]:=b[0];
     while (a[a[0]]=0) and (a[0]>1) do dec(a[0]);
end;

procedure pr;
var i:longint;
begin
     fillchar(z,sizeof(z),0);
     fillchar(h,sizeof(h),0);
     z[0]:=1; z[1]:=1;  h[0]:=1; h[1]:=1;
     for i:=n downto 1 do
     begin
          plus(h);
          if x>=p[i-1] then
          begin
               minus(z,h,z);
               x:=p[i]-1-x;
          end;
          plus(h);
          if y>=p[i-1] then
          begin
               minus(z,h,z);
               y:=p[i]-1-y;
          end;
     end;
     minus(z,h,z);
     wf;
end;

procedure init;
var i:longint;
begin
     p[0]:=1;
     for i:=1 to 41 do p[i]:=p[i-1]*2;
end;

begin
     assign(input,fi); reset(input);
     assign(output,fo); rewrite(output);
     init;
     rf;
     pr;
     read(x,y);
     y:=p[n]-1-y;
     pr;
     close(input); close(output);
end.

Code mẫu của ladpro98

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#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 TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); ++it)
#define RESET(a, v) memset((a), (v), sizeof((a)))
#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 BASE = 10000;
const int LEN = 4;
using namespace std;

typedef VI big;

void fix(big &a) {
    a.PB(0);
    FOR(i, 0, SZ(a) - 1) {
        a[i + 1] += a[i] / BASE; a[i] %= BASE;
        if (a[i] < 0) {a[i] += BASE; a[i + 1]--;}
    }
    while (SZ(a) > 1 && a.back() == 0) a.pop_back();
}

void operator += (big &a, big &b) {
    a.resize(max(SZ(a), SZ(b)));
    FOR(i, 0, SZ(b)) a[i] += b[i];
    fix(a);
}

void operator -= (big &a, big &b)
    {FOR(i, 0, SZ(b)) a[i] -= b[i]; fix(a);}

big operator + (big a, big b) {a += b; return a;}
big operator - (big a, big b) {a -= b; return a;}

LL lim, p, q, u, v;
big POW[100];

big ans(int k, LL x, LL y, big pos) {
    if (k == 0) return pos;
    big h = POW[lim - k << 1];
    LL mid = 1ll << (k - 1);
    bool uu = x < mid, ll = y < mid;
    if (ll  &&  uu) return ans(k - 1, x, mid - 1 - y, h - pos + big(1, 1));
    if (!ll &&  uu) return ans(k - 1, x, y - mid, h + h + h + pos);
    if (ll  && !uu) return ans(k - 1, mid * 2 - x - 1, mid - 1 - y, h + pos);
                    return ans(k - 1, mid * 2 - x - 1, y - mid, h + h + h - pos + big(1, 1));
}

ostream& operator << (ostream& cout, const big &a) {
    printf("%d", a.back());
    REPD(i, SZ(a) - 2, 0) printf("%04d", a[i]);
    return cout;
}

int main() {
    POW[0] = big(1, 1);
    FOR(i, 1, 100) POW[i] = POW[i - 1] + POW[i - 1];
    cin >> lim >> p >> q >> u >> v;
    cout << ans(lim, p, q, big(1, 1)) << ' ' << ans(lim, u, v, big(1, 1));
    return 0;
}

Code mẫu của RR

#include <iostream>
#include <algorithm>

#define FOR(i,a,b)  for(int i=a; i<=b; i++)
#define FORD(i,a,b) for(int i=a; i>=b; i--)
#define ll long long
#define P pair<ll,ll>
#define F first
#define S second
#define BASE 1000000000000000LL
#define LBASE 15
using namespace std;

int debug=0;
int k;
P lt2[80],i,j,one;

P operator + (P a,P b) {
    P c;
    c.S = a.S + b.S;
    int nho;
    if (c.S>=BASE) {
        nho=1;
        c.S-=BASE;
    }
    else nho=0;
    c.F = a.F + b.F + nho;
    return c;
}

P operator - (P a,P b) {
    P c;
    c.S = a.S - b.S;
    int nho;
    if (c.S>=0) nho=0;
    else {
        nho=1;
        c.S += BASE;
    }
    c.F = a.F - b.F - nho;
    return c;
}

P operator * (P a,ll k) {
    P c;
    c.S = a.S * k;
    int nho=c.S/BASE;
    c.S%=BASE;
    c.F = a.F * k + nho;
    return c;
}

void print(P a) {
    if (a.F) {
        cout<<a.F;
        char s[20];
        sprintf(s,"%lld",a.S);
        FOR(i,1,LBASE-strlen(s)) cout<<"0";
    }
    cout<<a.S;
}

void init() {
    lt2[0].S = 1;
    FOR(i,1,80)
        lt2[i]=lt2[i-1]*2;

    if (debug) FOR(i,0,80) print(lt2[i]);
}

void get(int u,P i,P j,P pos) {
    P res;
    if (u==0) {
        print(pos);
        return ;
    }
    if (i<lt2[u-1]) pos = pos+lt2[2*k-2*u];
    else {
        i = lt2[u]-i-one;
        pos = lt2[2*k - 2*u] + one - pos;
    }

    if (j<lt2[u-1]) {
        j = lt2[u-1]-j-one;
        pos = lt2[2*k - 2*u +1]+one-pos;
    }
    else {
        pos = pos+lt2[2*k-2*u+1];
        j = j - lt2[u-1];
    }

    get(u-1,i,j,pos);
}

void solve() {
    P pos;
    pos.F = 0; pos.S = 1;
    get(k,i,j,pos);
}

int main() {
    init();
    cin >>k;
    i.F = j.F = 0;
    one.F = 0; one.S = 1;
    cin >>i.S >>j.S;
    solve(); cout<<" ";
    cin >>i.S >>j.S;
    solve();
    return 0;
}

Code mẫu của khuc_tuan

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {

    static int[][] mh = {{0,-1},{1,0},{3,0},{2,-1}};
    static int[][] hm = { {0,0,1,0, 0,1,-1,-1}, {1,0,-1,-1, 0,1,-1,-1}, {0,0,1,0, 0,-1,1,0}, {1,0,-1,-1, 0,-1,1,0} };

    static long K, u, v, p, q;
    static BigInteger[] pow2;

    static void xet(long k, long u, long v, BigInteger vt) {
        if(k==0) {
            System.out.println(vt);
            return;
        }
        int t = (u>=(1L<<(k-1))) ? 1 : 0;
        if(v>=(1L<<(k-1))) t += 2;
        BigInteger nvt = BigInteger.ZERO;
        for(int tt=0;tt<mh[t][0];++tt) nvt = nvt.add(pow2[(int)((K-k)*2)]);
        if(mh[t][1]==-1) nvt = nvt.add(pow2[(int)(K-k)*2]).add(pow2[0]).subtract(vt);
        else nvt = nvt.add(vt);
        xet( k-1, hm[t][0]*(1L<<k)+hm[t][1]*(1L<<(k-1))+hm[t][2]*u+hm[t][3], 
                  hm[t][4]*(1L<<k)+hm[t][5]*(1L<<(k-1))+hm[t][6]*v+hm[t][7], nvt);
    }

    public static void main(String[] args) throws Exception {
        //BufferedReader kb = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc = new Scanner(System.in);
        K = sc.nextLong();
        u = sc.nextLong();
        v = sc.nextLong();
        p = sc.nextLong();
        q = sc.nextLong();
        pow2 = new BigInteger[100];
        pow2[0] = BigInteger.ONE;
        for(int i=1;i<=80;++i) pow2[i] = pow2[i-1].add(pow2[i-1]);
        xet( K, u, v, pow2[0]);
        xet( K, p, q, pow2[0]);
    }
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.