考虑由$x\ge 1$和$0\le y \le 1/x$所表示的区域。

记$S_1$是能够放进曲线下区域的最大正方形，$S_2$是能够放进排除$S_1$以后的区域的最大正方形，$S_3$是能够放进排除$S_1, S_2$以后的区域的最大正方形，以此类推。

每个$S_n$可以对应一个数对$(a, b)$，分别表示$S_n$左侧和下方的正方形数量。

如上图所示，$S_2$的左侧有一个正方形，下方没有正方形，因此对应$(1,0)$。

可以看出$S_{32}$和$S_{50}$均对应$(1,1)$。50也是对应$(1,1)$的最大下标。

求能对应$(3,3)$的最大下标。

本题难度:

解答

假定已知正方形左下角的坐标是$(x_0,y_0)$，并设右上角的坐标是$(x,y)$，则有 $$xy=1, \quad y-y_0=x-x_0.$$ 消去y可得 $$x^2+(y_0-x_0)x-1=0, $$ 从中可以解出x，从而$d=x-x_0$就是正方形的边长。接下来$(x_0+d,y_0)$和$(x_0,y_0+d)$都可以作为其它正方形的左下角。

先用深度优先搜索找出能对应$(3,3)$的正方形的最小边长m，栈中的数据$(x,y,a,b)$反别对应当前正方形左下角的坐标、左侧的正方形数，下方的正方形数。

再作一次深度优先搜索找出边长不小于m的正方形的数量即答案，栈中的数据$(x,y,d)$反别对应当前正方形左下角的坐标和边长。

结果是$782252$。

import math

def cal(x,y):
    b=y-x
    return 0.5*(math.sqrt(b*b+4)-b)-x

q=[(1,0,0,0)]
m=9999

while q:
    x,y,a,b=q.pop()
    d=cal(x,y)
    if a==b==3:
        m=min(m,d)
    else:
        if a < 3:
            q.append((x+d,y,a+1,b))
        if b < 3:
            q.append((x,y+d,a,b+1))

print "min size is", m

q=[(1,0,cal(1,0))]
r=0

while q:
    x,y,d=q.pop()
    r+=1
    d1,d2=cal(x+d,y),cal(x,y+d)
    if d1>=m:
        q.append((x+d,y,d1))
    if d2>=m:
        q.append((x,y+d,d2))

print r