旅行蚂蚁

平面上有一只蚂蚁要从点$A(0,1)$移动到点$B(d,1)$，其中d是一整数。

蚂蚁的移动轨迹由一系列线段组成，每段称为一步。

每一步开始时，设蚂蚁的位置为$(x_0, y_0)$，则它会选择一个满足$x1\ge0, y_1\ge 1$的整点$(x_1, y_1)$，并以速度$v$匀速向该点移动。v的取值如下：

若$y_0=y_1$，则$v=y_0$，否则$v=(y_1-y_0)/(\ln y_1-\ln y_0)$。

以下左图是当$d=4$时的一条路径。蚂蚁从点$A(0,1)$移动到点$P_1(1,3)$，速度为$(3-1)/(\ln 3-\ln 1)\approx 1.8205$，所需时间为$\sqrt 5/1.8205\approx1.2283$。

接下来它再从点$P_1(1,3)$移动到点$P_2(3,3)$，速度为$3$，所需时间为$2/3\approx0.6667$。

最后它从点$P_2(3,3)$移动到点$B(4,1)$，速度为$(1-3)/(\ln 1-\ln 3)\approx 1.8205$，所需时间为$\sqrt5/1.8205\approx1.2283$。

总耗时约为$1.2283+0.6667+1.2283=3.1233$。

右图则是另一条路径，总耗时约为$0.98026+1+0.98026=2.96052$，这也是$d=4$时的最快路径。

记$F(d)$为d所对应的最快路径的耗时，例如$F(4)\approx 2.960516287$。

可以验证$F(10)\approx4.668187834$以及$F(100)\approx9.217221972$。

求$F(10000)$，结果保留9位小数。

本题难度:

解答

本题是最速降线问题的一种变体，需要找出以$1/y$作为cost函数时从$A$到$B$的最小cost。

此时的最优路径其解析形式是以$AB$为直径的半圆，本题只能在整点间移动，因此设置一个上界（此处使用的是0.5），找到离半圆弧距离不超过此上界的点，在这些点上作动态规划即可。

最终结果是$18.420738199$。

注：为便于作除法、使用math.isqrt函数、以及格式化输出，以下代码为Python 3。

import math

n,n2,n3=10000,5000,100

threshold=0.5

v=lambda y0,y1:1.0*y if y0==y1 else (y1-y0)/(math.log(y1)-math.log(y0))
d=lambda x0,y0,x1,y1: math.sqrt((x1-x0)*(x1-x0)+(y1-y0)*(y1-y0))

P=[(i,j) for i in range(n2+1) for j in range(max(1,math.isqrt(n*i-i*i)-n3),min(n2+1,math.isqrt(n*i-i*i)+n3)) if abs(d(n2,0,i,j)-n2) < threshold]
res={}

for i,(x,y) in enumerate(P):
    if x==0 or y==1:
        res[x,y]=d(0,1,x,y)/v(1,y)
    else:
        res[x,y] = min(res[a,b]+d(a,b,x,y)/v(b,y) for (a,b) in P[max(0,i-n3):i])

print(f"{2*res[n2,n2]:.9f}")