分形之城

城市的规划在城市建设中是个大问题。

不幸的是，很多城市在开始建设的时候并没有很好的规划，城市规模扩大之后规划不合理的问题就开始显现。

而这座名为 Fractal 的城市设想了这样的一个规划方案，如下图所示：

当城区规模扩大之后，Fractal 的解决方案是把和原来城区结构一样的区域按照图中的方式建设在城市周围，提升城市的等级。

对于任意等级的城市，我们把正方形街区从左上角开始按照道路标号。

虽然这个方案很烂，Fractal 规划部门的人员还是想知道，如果城市发展到了等级 $N$，编号为 $A$ 和 $B$ 的两个街区的直线距离是多少。

街区的距离指的是街区的中心点之间的距离，每个街区都是边长为 $10$ 米的正方形。

输入格式

第一行输入正整数 $n$，表示测试数据的数目。

以下 $n$ 行，输入 $n$ 组测试数据，每组一行。

每组数据包括三个整数 $N,A,B$，表示城市等级以及两个街区的编号，整数之间用空格隔开。

输出格式

一共输出 $n$ 行数据，每行对应一组测试数据的输出结果，结果四舍五入到整数。

数据范围

$1≤N≤31$,
$1≤A,B≤2^{2N}$,
$1≤n≤1000$

输入样例

3 
1 1 2 
2 16 1 
3 4 33 

输出样例

10 
30 
50 

解析

大模拟题，思路简单

首先解决三个问题

①：如何从 [等级一] 的图像变化成 [等级二] 的图像

②：给你 [等级二] 图像中的某个点，如何找出该点在 [等级一] 图像中的对应点

③： 如何将上面的思路运用到更高等级的图像中

先解决 ①

懒，不想画图，给一张写题的草稿图，请自行找张纸根据我说的一边画一边看

我简单的令 等级一的图像 为 1图，等级二的图像 为 2图。将 2图 以四个房子为一个象限，图像的中点为原点，右为正x，上位正y 作一个坐标轴。取出 2图 中的四个象限图像，以 1图 样式摆放。

此时我们可以得到 4个4方格图像，分别代表的是 2图 的 “第一象限” “第二象限” “第三象限” 第四象限“

此时再以图像的中点为原点，右为正x，上为正y 作一个坐标轴，可以得到四个点分别在四个象限的图像。

此时 我们将四个图像的各编号以从小到大的顺序重新编号为 1、2、3、4，再将这四个图像与 1图 作比较。

这里挑一个最难的说

第二象限图像：是 1图 以坐标原点顺时针旋转90°，再以 y轴 作左右对称得到的图形，观察坐标变化

1：(-1,1) -> (-1,1)

2：(1,1) -> (-1,-1)

3：(1,-1) -> (1, -1)

4：(-1,-1) -> (1,1)

即可得，变化式为

(x,y) -> (y,x) ->(-y,-x)

这样就可以从 1图 变成第二象限图像，再将此图像移动至 2图 的第二象限处 即（令一个方格的长度为len）

(-y + len / 2,-x - len / 2)

剩下的象限图像同理

第一象限图像：(x + len / 2, y + len / 2)

第三象限图像：(y - len / 2, x - len / 2)

第四象限图像：(x + len / 2, y - len / 2)

于是此时我们就解决了 ①

考虑 ②，我们发现 2图 的每个象限图的点上的数去减一 Mod 一图的点总数 再加一，就可以得到 2图 每个象限的个点 在 1图上的对应点。于是②解决

考虑③，对照题中给的 3图 与 2图 的图像，我们发现与 2图 和 1图 的对应关系是相同的，那么我们继续套用 1图 到 2图 的公式 进 2图 到 3图即可，毕竟我们只需要做到点的对应，一个递归解决。

那么根据上面的 ①②③，我们就可以写出代码

#include <cmath>
#include <cstdio>
#include <iostream>
//前排提醒 我的递归写的较差，更简单的可以看yxc的代码
long long n;

struct Coordinates{
	long long x, y;
};

Coordinates Tem;
void init() {
	Tem.x = 0;
	Tem.y = 0;
}

Coordinates Calculate(long long x, long long k) {
	long long len = (1ll << (x - 1)) * 10; //每个象限的总长度
	long long cnt = (k - 1) / (1ll << (x * 2 - 2)); //该点在第几象限
	long long tnt = ((k - 1) % (1ll << (x * 2 - 2))) + 1; //该点对应上一级的哪个点
	
	if(x == 1) { //如果到等级一了 就给坐标值
		if(k == 1) Tem.x = -5, Tem.y = 5;
		if(k == 2) Tem.x = 5, Tem.y = 5;
		if(k == 3) Tem.x = 5, Tem.y = -5;
		if(k == 4) Tem.x = -5, Tem.y = -5;
		return Tem;
	}
	
	Calculate(x - 1, tnt); //返回到前一级
	Tem.x = Tem.x + len / 2; //我这里的意思是 先统一移动到第一象限
	Tem.y = Tem.y + len / 2; //因为我下面的公式都是以第一象限来推的
	if(cnt == 0) { //如果在第二象限
		long long x1, y1;
		x1 = Tem.x, y1 = Tem.y;
		Tem.x = -y1, Tem.y = -x1 + len;
	}
	//第一象限我已经移动过了 所以不用写
	if(cnt == 2) { //如果在第四象限
		Tem.y = Tem.y - len;
	}
	
	if(cnt == 3) { //如果在第三象限
		long long x1, y1;
		x1 = Tem.x, y1 = Tem.y;
		Tem.x = y1 - len, Tem.y = x1 - len;
	} return Tem;
}

int main() {
	long long N, a, b;
	scanf("%ld", &N);
	init();
	while(N--) {
		scanf("%ld %ld %ld", &n, &a, &b);
		Coordinates k = Calculate(n, a); init(); //重置一下
		Coordinates m = Calculate(n, b); init();
		double x = k.x - m.x, y = k.y - m.y; //两点距离公式
		printf("%.0lf\n", sqrt(x * x + y * y));
	} return 0;
}