使用四叉树编码，我们能将一个$2^N\times 2^N$大小的黑白图片表示为一个二进制串，该比特串可以按如下方式从左到右递归解读为：

0表示对当前区域作分割，即将当前的$2^m\times 2^m$区域分割为四个$2^{m-1}\times2^{m-1}$的区域，其后的二进制位分别描述分割后左上、右上、左下、右下的信息。

10表示当前区域只包含黑色像素。

11表示当前区域只包含白色像素。

例如以下的$4\times 4$图象（彩色点表示可以作分割位置）可以表示长度为30的编码001010101001011111011010101010，也可以表示为长度为$16$的编码0100101111101110。

16也是最短的、可以描述这幅图象的二进串长度。

给定正整数N，记$D_N$是按照如下染色方案所得的$2^N\times2^N$图像：

原点在左下角，若$(x -2^{N-1})^2 + (y-2^{N-1})^2\le2^{2N-2}$，则$(x,y)$处的像素为黑色，否则为白色。

可以描述$D_{24}$的二进串的最短长度是多少？

本题难度:

解答

容易看出$(x -2^{N-1})^2 + (y-2^{N-1})^2\le2^{2N-2}$对应的$(x,y)$是圆形内部的格点，四个区域可以相互通过水平和垂直的对称变换得到。

记C为点$(2^{N-1},2^{N-1})$，用$(x,y,z)$表示距离C最近的角的坐标是$(x,y)$，且大小为z的正方形区域，递归计算即可得结果$313135496$。

bound=1<<46
m=1<<23

def check(x,y,z):
    if (x-m)*(x-m)+(y-m)*(y-m)>bound or (x+z-1-m)*(x+z-1-m)+(y+z-1-m)*(y+z-1-m)<=bound:
        return 2
    if z==2:
        return 9
    z/=2
    return check(x,y,z)+check(x+z,y+z,z)+check(x+z,y,z)+check(x,y+z,z)+1

print check(m,m,m)+check(m+1,m,m)*2+check(m+1,m+1,m)+1