## 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
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;
y:=p[n]-1-y;
pr;
close(input); close(output);
end.


#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;
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 {
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;