有三个排成一行，中间用自动门连接的房间。

（左：起点；右：终点）

每扇门都可用安保卡打开，每张安保卡只能使用一次，且进入房间后门就会自动关闭。

起点处有一台分发机能无限量提供安保卡，每个房间中都有一个容量无限的箱子可以存放安保卡安保卡。

若只能携带三张卡，那么显然不使用箱子就无法到达终点。

使用箱子的话则最少只需使用总共六张卡即可到达终点，具体方案是先使用一张卡进入房间1，在箱子里放一张卡，再是身上最后一张卡回到起点。然后再取出三张卡，使用一张进入房间1，取出箱子中的卡，如此则身上又有三张卡，恰好能穿过三道们到达终点。

类似地，通过六个房间最少需要总计123张卡。

记C是允许携带的卡的数量，R是要通过的房间数目，M(C,R)为此时通过所有房间最少需要的卡的数量。

可以验证，$ M(3,6)=123, M(4,6)=23$，以及$\sum_{C=3}^{10}M(C,10)=10382$。

求$\sum_{C=3}^{40}M(C,30)$。

本题难度:

解答

显然若$R < C$，则$M(C,R)=R+1$，否则需要通过先将充分多的卡片运到房间一，再以房间一为起点继续这一过程。

每次从起点往返可以运输$C-2$张卡片，最后一次不需要再返回起点，因此可以运输$C-1$张，递归计算即得结果$34315549139516$。

注：因需使用cache装饰器作记忆化搜索，以下为Python 3代码。

from functools import *

@cache
def M(C,R):
    if R < C:
        return R+1
    t=M(C,R-1)
    r=(t-C+1)%(C-2)
    return ((t-C+1)//(C-2)+1)*C+(r+2)*(r>0)

print(sum(M(c,30) for c in range(3,41)))