当前位置:首页 » Project Euler » 详细页

Magic 5-gon ring 题号:68 难度: 25 中英对照

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.

TotalSolution Set
94,2,3; 5,3,1; 6,1,2
94,3,2; 6,2,1; 5,1,3
102,3,5; 4,5,1; 6,1,3
102,5,3; 6,3,1; 4,1,5
111,4,6; 3,6,2; 5,2,4
111,6,4; 5,4,2; 3,2,6
121,5,6; 2,6,4; 3,4,5
121,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?



Solution

我们可对下面的魔力五边形进行编号,取左上角的点标记为 $0$,按顺时针顺序将外层依次标记上 $1,2,3,4$ 。再对内层的上顶点标记为5,再按顺时针顺序将内层依次标记上$5,6,7,8,9$。用数组表示这几个点 $state[i],i\le9$ ![图片](https://projecteuler.net/project/images/p068_2.gif) 我们将数字$1,2,3,4,5,6,7,8,9,10$ 的不同排序依次放入$state[0],state[1],…,state[9]$,当满足每条线上的数字和相同,即 $$state[0] + state[5] + state[6]=state[1] + state[6] + state[7]=state[2] + state[7] + state[8]=state[4] + state[9] + state[5]$$ 再找出外层中的最小值,即 $state[0],state[1],…,state[4]$的最小值,按顺时针的顺序依次将每条边的上的数字拼接在一起,构成 $s$ 。当拼接数字 $s$ 为16位时,与当前最大值 $Max$ 比较,若大于,则更新 $Max$ 为 $s$。当取遍 $1,2,3,4,5,6,7,8,9,10$ 的所有排序时,返回$Max$值。

Code

public final class p68  {
	
	public static void main(String[] args) {
		long start = System.nanoTime();
		long result = run();
        long end = System.nanoTime();
		System.out.println( result );
		System.out.println (( end - start )/1000000 +"ms");	
	}
	
	public static long run() {
		int[] state = new int[10];
		for (int i = 0; i < state.length; i++)
			state[i] = i + 1;
		
		String max = null;
		do {
			int sum = state[0] + state[5] + state[6];
			if (   state[1] + state[6] + state[7] != sum
			    || state[2] + state[7] + state[8] != sum
			    || state[3] + state[8] + state[9] != sum
			    || state[4] + state[9] + state[5] != sum)
				continue;
			
			int minOuterIndex = -1;
			int minOuter = Integer.MAX_VALUE;
			for (int i = 0; i < 5; i++) {
				if (state[i] < minOuter) {
					minOuterIndex = i;
					minOuter = state[i];
				}
			}
			
			String s = "";
			for (int i = 0; i < 5; i++)
				s += "" + state[(minOuterIndex + i) % 5] + state[(minOuterIndex + i) % 5 + 5] + state[(minOuterIndex + i + 1) % 5 + 5];
			if (s.length() == 16 && (max == null || s.compareTo(max) > 0))
				max = s;
		} while (nextPermutation(state));
		
		if (max == null)
			throw new AssertionError();
		return Long.valueOf(max);
	}
	//取下一个排序,直到所有的数字是按降序排列的为止。
	public static boolean nextPermutation(int[] a) {
		int n = a.length, i, j;
		for (i = n - 2; ; i--) {
			if (i < 0)
				return false;
			if (a[i] < a[i + 1])
				break;
		}
		for (j = 1; i + j < n - j; j++) {
			int tp = a[i + j];
			a[i + j] = a[n - j];
			a[n - j] = tp;
		}
		for (j = i + 1; a[j] <= a[i]; j++);
		int tp = a[i];
		a[i] = a[j];
		a[j] = tp;
		return true;
	}
	
}
6531031914842725
52ms