cpp
//分治法
/*
旋转矩阵:[逆时针]
cosθ -sinθ
sinθ cosθ
逆时针转90°
代入θ = 90°
0 -1
1 0
对[x,y]作用
[x,y]->[-y,x]
顺时针转90° ->逆时针转270°
代入θ = 270°
0 1
-1 0
对[x,y]作用
[x,y]->[y,-x]
*/
/*
n级图 -> 4个n-1级图
标号 0 1
2 3
注意坐标系是:
|--------> y
|
|
|
x
0:相当于 旋转 + 翻转 n-1级图 顺时针转90° 再 水平翻转
[x,y] -> [y,x]
1: 相当于 +偏移量
[x,y] -> [x,y+len]
2:相当于 +偏移量
[x,y] -> [x+len,y+len]
3: 相当于 旋转 + 翻转 + 偏移量 n-1级图 逆时针转90° 再 水平翻转 再加偏移量
[x,y] -> [2*len-1 -y,len-1 -x]
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define int long long
using PII = pair<long long,long long>;
#define x first
#define y second
PII calc(int n,int k){
//terminator
if(n == 0) return {0,0};
//process the current logic and drill down
int len = 1ll<<(n-1);
int cnt = 1ll<<(n-1)*2;
PII pos = calc(n-1,k%cnt); //取余:获取在n-1级图中的位置
int kx = pos.x; int ky = pos.y;
int op = k/cnt; //n级图有n-1级图 对应在哪个分块 进行相应的操作
if(op==0) {
return {ky,kx};
}
else if(op == 1){
return {kx,ky+len};
}
else if(op == 2){
return {kx+len,ky+len};
}
else {
return {2*len-1-ky,len-1-kx};
}
}
signed main()
{
int T;
cin>>T;
while(T--){
int n,a,b;
cin>>n>>a>>b;
//从0开始编号 方便取模
PII pa = calc(n,a-1);
PII pb = calc(n,b-1);
double dx = pa.x - pb.x;
double dy = pa.y - pb.y;
printf("%.0lf\n",sqrt(dx*dx + dy*dy)*10); //四舍五入
}
return 0;
}