题目68：一个“魔术”五角环所能形成的最大的16位字符串是什么？

欧拉计划

Magic 5-gon ring

Consider the following "magic" 3-gon ring, filled with the numbers 1 to 6, and each line adding to nine.



Working clockwise, and starting from the group of three with the numerically lowest external node (4,3,2 in this example), each solution can be described uniquely. For example, the above solution can be described by the set: 4,3,2; 6,2,1; 5,1,3.

It is possible to complete the ring with four different totals: 9, 10, 11, and 12. There are eight solutions in total.

Total        Solution Set
9        4,2,3; 5,3,1; 6,1,2
9        4,3,2; 6,2,1; 5,1,3
10        2,3,5; 4,5,1; 6,1,3
10        2,5,3; 6,3,1; 4,1,5
11        1,4,6; 3,6,2; 5,2,4
11        1,6,4; 5,4,2; 3,2,6
12        1,5,6; 2,6,4; 3,4,5
12        1,6,5; 3,5,4; 2,4,6
By concatenating each group it is possible to form 9-digit strings; the maximum string for a 3-gon ring is 432621513.

Using the numbers 1 to 10, and depending on arrangements, it is possible to form 16- and 17-digit strings. What is the maximum 16-digit string for a "magic" 5-gon ring?

题目：

考虑如下的“魔术”三角环：该环被1到6的数字填充，并且每一行的和为 9。



按照顺时针顺序，从外部节点最小的三个为一组的组开始（该例中为4,3,2），每一组解都可以被唯一描述。例如，上图所示的解可以被描述为集合： 4,3,2; 6,2,1; 5,1,3。

这个环还可以被用四个不同的和来完成。一共有八组解

和                   解
9          4,2,3; 5,3,1; 6,1,2
9          4,3,2; 6,2,1; 5,1,3
10        2,3,5; 4,5,1; 6,1,3
10        2,5,3; 6,3,1; 4,1,5
11        1,4,6; 3,6,2; 5,2,4
11        1,6,4; 5,4,2; 3,2,6
12        1,5,6; 2,6,4; 3,4,5
12        1,6,5; 3,5,4; 2,4,6

将每组解的数字连接起来，可以得到一个 9 位的字符串；三角环所能形成的最大字符串为 432621513。

使用数字 1 到 10，通过不同的安排，可以得到 16 位或 17 位的字符串。五角环所能形成的最大的 16 位的字符串是什么？

jerryxjr1220

这题其实挺简单的，无非就是排列组合问题，10个空格填上1~10个数字，由于是取16位数字中最大的，所以10一定是在外圈，在内圈的话就是17位数字了。
代码：

1. from itertools import permutations as pt
   
2. maxi = 0
   
3. for each in pt(range(1,11)):
   
4.         if 10 in each[5:]: continue
   
5.         if each[0]+each[5]+each[6]==each[1]+each[6]+each[7]==each[2]+each[7]+each[8]==each[3]+each[8]+each[9]==each[4]+each[9]+each[5]:
   
6.                 s=''.join([str(each[0])+str(each[5])+str(each[6])+str(each[1])+str(each[6])+str(each[7])+str(each[2])+str(each[7])+str(each[8])+str(each[3])+str(each[8])+str(each[9])+str(each[4])+str(each[9])+str(each[5])])
   
7.                 if len(s)==16 and each[0]==min(each[0:5]):
   
8.                         maxi = max(maxi,int(s))
   
9. print(maxi)

复制代码

输出：
6531031914842725
[Finished in 1.7s]

原本以为会用很长时间，结果才1.7秒就出结果了。

gunjang

1. #Using the numbers 1 to 10, and depending on arrangements,
   
2. #it is possible to form 16- and 17-digit strings.
   
3. #What is the maximum 16-digit string for a “magic” 5-gon ring?
   
4. '''
   
5. 1+2+...10=55, inner five digits min is 12345=15, max is 678910=40
   
6. so average sum of three digit is 14(55+15) to 19(55+40)
   
7. 16-digit,so 10 is in outer five digit
   
8. inner max is 35, average sum of 3digit is (55+35)/5=18
   
9. '''
   
10. import itertools,time
    
11. 
    
12. def checkThreeGonRing(rings):
    
13.         r = []
    
14.         for three in rings:
    
15.                 r.extend(three)
    
16.         r = sorted(set(r))
    
17.         return r == list(range(1,11))
    
18. 
    
19. def to16digitstring(rings):
    
20.         r = ''
    
21.         for three in rings:
    
22.                 for i in three:
    
23.                         r += str(i)               
    
24.         return int(r)
    
25. 
    
26. def getmax16digit():
    
27.         maxstr = 0
    
28.         for inner5 in itertools.permutations(list(range(1,10)), 5):
    
29.                 average5 = (55+sum(inner5)) // 5
    
30.                 threeGonRing = []
    
31.                 for i in range(5):
    
32.                         outerdigit = average5 - inner5[i] - inner5[(i+1)%5]
    
33.                         threeGonRing.append((outerdigit, inner5[i], inner5[(i+1)%5]))
    
34.                 if not checkThreeGonRing(threeGonRing):
    
35.                         continue
    
36.                 outerDs = [x[0] for x in threeGonRing]
    
37.                 lowestindex = outerDs.index(min(outerDs))
    
38.                 if lowestindex != 0:
    
39.                         threeGonRing = threeGonRing[lowestindex:] + threeGonRing[:lowestindex]
    
40.                 #threeGonRing.sort(key= lambda x : x[0]) #incorrect
    
41.                 s = to16digitstring(threeGonRing)
    
42.                 if s > maxstr:
    
43.                         maxstr = s
    
44. 
    
45.         return maxstr
    
46. 
    
47. st = time.time()
    
48. print(getmax16digit()) #6531031914842725
    
49. print('cost {0}s'.format(time.time()-st)) #0.09700536727905273s
    

复制代码

najin

不需要用编程，结果是
6531031914842725

grf1973

'分析：按题意，要从最外侧结点所填的数最小的线开始，可知外圈最小为6，且外圈五数必为6，7，8，9，10（可反证）
'因此，内圈为1，2，3，4，5。每条线数字之和为（2*内圈和+外圈和）/5=14
'进一步分析：第一条线第一个数为6，另两数之和即为8，考察（1，2，3，4，5），只能是3+5=8。因为取大数，所以第一条线为6-5-3
'在此基础上暴搜即可。按顺序针次序为每一节点编号：（6-5-3）-（w1-3-n1）-（w2-n1-n2）-（w3-n2-n3）-（w4-n3-5），其中外圈w=7 to 10，内圈n为1，2，4
'''
def euler068():                                            
    import itertools
    s=14   
    for (w1,w2,w3,w4) in itertools.permutations([7,8,9,10],4):   #外圈
        for (n1,n2,n3) in itertools.permutations([1,2,4],3):    #内圈
            if w1 + 3 + n1 == w2 + n1 + n2 == w3 + n2 + n3 == w4 + n3 + 5 == s:
                return("653%d%d%d%d%d%d%d%d%d%d%d%d"%(w1,3,n1,w2,n1,n2,w3,n2,n3,w4,n3,5))

print(euler068())

debuggerzh

有小学奥数题内味儿了

guosl

穷举死做也很快

1. /*
   
2. 答案：6531031914842725
   
3. 耗时：0.0150001秒
   
4. */
   
5. #include <iostream>
   
6. #include <algorithm>
   
7. #include <string>
   
8. using namespace std;
   
9. 
   
10. const int nSteps = 10;
    
11. 
    
12. int main(void)
    
13. {
    
14.   int a[10] = { 1,2,3,4,5,6,7,8,9,10 };
    
15.   long long nMax = 0;
    
16.   do
    
17.   {
    
18.     if (a[0] > a[1] || a[0] > a[2] || a[0] > a[3] || a[0] > a[4])
    
19.       continue;
    
20.     int nS[5];
    
21.     nS[0] = a[0] + a[5] + a[6];
    
22.     nS[1] = a[1] + a[6] + a[7];
    
23.     nS[2] = a[2] + a[7] + a[8];
    
24.     nS[3] = a[3] + a[8] + a[9];
    
25.     nS[4] = a[4] + a[9] + a[5];
    
26.     if (nS[0] == nS[1] && nS[0] == nS[2] && nS[0] == nS[3] && nS[0] == nS[4])
    
27.     {
    
28.       string str = "";
    
29.       str += (a[0] < 10) ? string(1, char(a[0] + 48)) : string("10");
    
30.       str += (a[5] < 10) ? string(1, char(a[5] + 48)) : string("10");
    
31.       str += (a[6] < 10) ? string(1, char(a[6] + 48)) : string("10");
    
32.       str += (a[1] < 10) ? string(1, char(a[1] + 48)) : string("10");
    
33.       str += (a[6] < 10) ? string(1, char(a[6] + 48)) : string("10");
    
34.       str += (a[7] < 10) ? string(1, char(a[7] + 48)) : string("10");
    
35.       str += (a[2] < 10) ? string(1, char(a[2] + 48)) : string("10");
    
36.       str += (a[7] < 10) ? string(1, char(a[7] + 48)) : string("10");
    
37.       str += (a[8] < 10) ? string(1, char(a[8] + 48)) : string("10");
    
38.       str += (a[3] < 10) ? string(1, char(a[3] + 48)) : string("10");
    
39.       str += (a[8] < 10) ? string(1, char(a[8] + 48)) : string("10");
    
40.       str += (a[9] < 10) ? string(1, char(a[9] + 48)) : string("10");
    
41.       str += (a[4] < 10) ? string(1, char(a[4] + 48)) : string("10");
    
42.       str += (a[9] < 10) ? string(1, char(a[9] + 48)) : string("10");
    
43.       str += (a[5] < 10) ? string(1, char(a[5] + 48)) : string("10");
    
44.       if (str.length() == 16)
    
45.       {
    
46.         long long nTemp = atoll(str.c_str());
    
47.         nMax = max(nMax, nTemp);
    
48.       }
    
49.     }
    
50.   }
    
51.   while(next_permutation(a, a + 10));
    
52.   cout << nMax << endl;
    
53.   return 0;
    
54. }
    

复制代码

TLM

6531031914842725
Time:0.0s

1. import time
   
2. st=time.time()
   
3. # 中间会出现两次，外围出现一次，16位意味着10出现在外围。
   
4. # 为了使数字尽可能地大，最高位尽可能大，外围最小值也要尽可能的大，所以一半以上的数字在外围，一半以下的在内圈
   
5. n=5
   
6. # 内圈计算两次，加上外围数字，除以n就知道和为多少了
   
7. num=(1+2*n)+(1+n)//2
   
8. l=list(range(1,n+1))
   
9. ans=''
   
10. ans=ans+str(n+1)
    
11. ans=ans+str(n)
    
12. ans=ans+str((1+n)//2)
    
13. a=(1+n)//2
    
14. # 后面不出错，应该需要数学证明。理论上不难
    
15. for i in range(2*n,n+1,-1):
    
16.     ans=ans+str(i)
    
17.     ans=ans+str(a)
    
18.     a=num-i-a
    
19.     ans=ans+str(a)
    
20. print(ans)
    
21. print('Time:{}s'.format(time.time()-st))

复制代码