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

Counting the number of "hollow" square laminae that can form one, two, three, ... distinct arrangements 题号:174 难度: 40 中英对照

We shall define a square lamina to be a square outline with a square "hole" so that the shape possesses vertical and horizontal symmetry.

Given eight tiles it is possible to form a lamina in only one way: 3x3 square with a 1x1 hole in the middle. However, using thirty-two tiles it is possible to form two distinct laminae.

If t represents the number of tiles used, we shall say that t = 8 is type L(1) and t = 32 is type L(2).

Let N(n) be the number of t ≤ 1000000 such that t is type L(n); for example, N(15) = 832.

What is ∑ N(n) for 1 ≤ n ≤ 10?


Solution

首先明确题意 - 由n^2个小正方形组成的大正方形正中间挖去m^2个小正方形组成的大正方形后,剩下的小正方形个数为$$number=n^{2}-m^{2}$$ - 那么假设对于number个边缘正方形个数,n和m的取值有N对 - 题目要求在边缘正方形的number小于1000000时,满足n和m的取值对N大于等于1且小于等于10的number的个数 理清了思路,那么在求解时的重点在于求N[number],需要两层循环 - 第一层循环:n 1.n的最小值应为3(取值为1和2时,内层不能从中心挖去m个正方形) 2.最大值是一个大正方形最外面一层的小正方形个数正好为1000000,即$$(n-1)*4<=1000000$$ - 第二层循环:m 1.m的最小值为1 2.m的最大值为n-2(边缘正方形只有最外面一层的情况) 3.注意m的取值应该是以2为单位加减,因为要保证是在中心 这样通过两层循环,就可以求出范围内时的N[number],要注意在循环内要判断$$n^{2}-m^{2}<=1000000$$因为循环时n的最大值是在假设边长为n的正方形仅最外面一层正方形的个数就达到1000000的情况,所以要避免出现n过大,m过小以致边缘正方形的个数number超出范围的情况 最后输出满足$$N[number]>=1$$且$$N[number]<=10$$的number个数

Code

import java.util.Arrays;

public final class p174 {
	private static final int MAX_N=1000000;
	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[] N=new int[MAX_N+1];
		Arrays.fill(N,0);
		for(int n=3;(n-1)*4<=MAX_N;n++){
			for(int m=n-2;m>=1;m=m-2){
				int number=n*n-m*m;
				if(number>MAX_N){
					break;
				}
				N[number]++;
			}
		}
		long ans=0;
		for(int i=0;i<=MAX_N;i++){
			if(N[i]>=1&&N[i]<=10){
				ans++;
			}
		}
		return ans;
	}
}
209566
39ms