0068 魔力五边形环
* * * *
拉格朗日计划
* * * *
魔力五边形环

考虑下面这个“魔力”三角形环,把1至6这六个数按一定顺序填入,可以令每条线上的三个数加起来都是9。



对每种填法,我们用如下方式唯一表示之:

从最外侧节点最小的数所在的线(在上例中是4-3-2所在的线)开始,以顺时针方向方向由外向内枚举每条线上的数。例如,上例可以记作:4-3-2;6-2-1;5-1-3。把这些数字连接起来,得到一个九位的、由数字组成的字符串432621513。

能令每条线上的数字之和相等的填法共有以下八种,相应的线数字和分别是9、10、11、12:

4-2-3; 5-3-1; 6-1-2,线数字和是9。

4-3-2; 6-2-1; 5-1-3,线数字和是9。

2-3-5; 4-5-1; 6-1-3,线数字和是10。

2-5-3; 6-3-1; 4-1-5,线数字和是10。

1-4-6; 3-6-2; 5-2-4,线数字和是11。

1-6-4; 5-4-2; 3-2-6,线数字和是11。

1-5-6; 2-6-4; 3-4-5,线数字和是12。

1-6-5; 3-5-4; 2-4-6,线数字和是12。

这一集合中最大的数字正是43262151。

现考虑在如下的”魔力“五边形环中填入1至10,用上文的方式记录填法后连接可得一个十六位或十七位的、由数字组成的字符串。



若仍要求每条线上的数字之和相等,则在相应的填法所生成的十六位字符串中按字典序最大的是多少?

本题难度:



解答

一共只有$10!=3628800$种情况,直接暴力枚举即得结果$6531031914842725$。

import itertools
m=""
for d in itertools.permutations([1,2,3,4,5,6,7,8,9,10]):
    c=2*sum(d[:5])+sum(d[5:])
    if c in [70,75,80,85,90,95]:
        z=c/5
        if d[5]+d[0]+d[1]==z and d[6]+d[1]+d[2]==z and d[7]+d[2]+d[3]==z and d[8]+d[3]+d[4]==z and d[9]+d[4]+d[0]==z:
            i=d.index(min(d[5:]))
            s=""
            for j in range(i,i+5):
                k=j if j < 10 else j-5
                s=s+str(d[k])+str(d[k-5])+str(d[(k-4)%5])
            m=max(m,s)
print m