三角形数、正方形数、五边形数、六边形数、七边形数和八边形数等等统称为多边形数。它们分别由如下的公式给出：

三角形数：$P_3(n)=n(n+1)/2$

正方形数：$P_4(n)=n^2$

五边形数：$P_5(n)=n(3n-1)/2$

六边形数：$P_6(n)=n(2n-1)$

七边形数：$P_7(n)=n(5n-3)/2$

八边形数：$P_8(n)=n(3n-2)$

有序数组(8128,2882,8281)中的三个数分别是三角形数（$P_3(127)=8128$）、正方形数（$P_4(91)=8281$）和五边形数（$P_5(44)=2882$），每个数的后两位都是其后一个数的前两位、且最后一个数的后两位也是第一个数的前两位。这也是唯一一个满足上述性质的、由四位数构成的有序数组。

存在由四位数构成的六元有序数组$(a_0,\ldots,a_5)$，其中的六个数分别是三角形数、正方形数、五边形数、六边形数、七边形数和八边形数，且$a_i$的后两位是$a_{i+1}$的前两位，$i\in\mathbb Z_6$。求该数组中的元素和。

本题难度:

解答

首先生成所有的四位多边形数, 将它们按照类型存在六个字典中，字典的键值是其前两位数字。

接下来作深度优先搜索即得结果8256, 5625, 2512, 1281, 8128, 2882, 它们的和是$28684$。

d=[{},{},{},{},{},{}]
for n in range(200):
    for i,t in enumerate([n*(n+1)/2, n*n, n*(3*n-1)/2, n*(2*n-1), n*(5*n-3)/2, n*(3*n-2)]):
        if t>999 and t < 10000:
            if t/100 in d[i]:
                d[i][t/100].append(t%100)
            else:
                d[i][t/100]=[t%100]

t=[[[u*100+v],[1,2,3,4,5]] for u in d[0] for v in d[0][u]]    
found=False
while not found:
    s,c=t.pop()
    if c:
        z=s[-1]%100
        for i in c:
            if z in d[i]:
                for y in d[i][z]:
                    t.append([s+[z*100+y],[j for j in c if j!=i]])
    else:
        if s[-1]%100==s[0]/100:
            found=True
            print sum(s),s