设有一个未知的$\{1, 2, \ldots, n\}$中的数x，需要通过提问的方式找到该数。

每次提问的内容是该集合中的一个数k，得到的回答是未知数比k小，比k大，等于k这三者之一，提问的成本等于k。

给定n，最优策略是值最坏情况下总成本最小的策略。

例如$n=3$时最优选择是2，根据答案可以直接确定未知数。

又如$n=8$时，若使用二分策略，那么最坏情况的总成本至少是17，这是因为若x=8，就需要依次提问4、6、7，总成本为$4+6+7=17$。

但若将第一次的问题改为5，使用5->7的提问顺序可以确定所有大于5的x，而使用5->3->1的提问顺序可以确定所有小于5的x，因此该策略最差情况的总本是$\max(5+7,5+3+1)=12$。

事实上这也是$n=8$时的最优策略。

记$C(n)$为n的最优策略在最坏情况下的成本，可以验证$C(1)=0, C(2)=1, C(3)=2, C(8)=12, C(100)=400$以及$\sum_{n=1}^{100}C(n)=17575$。

求$\sum_{n=1}^{200000}C(n)$。

本题难度:

解答

本题除了按要求分治计算以外没有太好的手段，不过可以注意到：

（1）当n为2的幂减2时$C(n)$就是标准二分查找的得到的结果，因此可以将这种情况缓存。

（2）其它情形的关键在于每个n的第一个分支点，对分支点以下的部分可以递归计算，分支点以上的部分可以经过平移后递归计算。

（3）分支点只在2的幂附近发生改变，可以通过预处理缓存。

最终结果是$260511850222$。

f={0:(0,0),2:(1,1),6:(2,8),14:(3,31),30:(4,94),62:(5,253),126:(6,636),254:(7,1531),510:(8,3578),1022:(9,8185),2046:(10,18424),4094:(11,40951),8190:(12,90102),16382:(13,196597)}

g=(1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383)

def cal(a,b):
    if b-a in f:
        return f[b-a][0]*a+f[b-a][1]
    i=0
    while i < len(g) and g[i] < b-a:
        i+=1
    c=min(a+g[i-1],b-(g[i-1]-1)/2)
    return c+max((cal(a,c-1),cal(c+1,b)))

c=[0,0,1,2,4,6,8]
q=[0,4,8,16,32,64,128]
i,a,n=2,3,6
while n < 200000:
    n+=1
    i+=(a>4**i)
    s,a=min((n-a-p+max((c[n-a-p-1],cal(n-a-p+1,n))),a+p) for p in q[:i] if 0 < n-a-p < n)
    c.append(s)

print sum(c)