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

Cuboid layers 题号:126 难度: 55 中英对照

The minimum number of cubes to cover every visible face on a cuboid measuring 3 x 2 x 1 is twenty-two.


If we then add a second layer to this solid it would require forty-six cubes to cover every visible face, the third layer would require seventy-eight cubes, and the fourth layer would require one-hundred and eighteen cubes to cover every visible face.

However, the first layer on a cuboid measuring 5 x 1 x 1 also requires twenty-two cubes; similarly the first layer on cuboids measuring 5 x 3 x 1, 7 x 2 x 1, and 11 x 1 x 1 all contain forty-six cubes.

We shall define C(n) to represent the number of cuboids that contain n cubes in one of its layers. So C(22) = 2, C(46) = 4, C(78) = 5, and C(118) = 8.

It turns out that 154 is the least value of n for which C(n) = 10.

Find the least value of n for which C(n) = 1000.


Solution

考虑一个$x\times y\times z$的立方体,设其覆盖$k$层需要的方块数量为$C(x,y,z,k)$,则: **第一层** 显然的有$C(x,y,z,1)=2(xy+yz+xz)$ **第二层** 首先在最上(下)、最左(右)、最前(后)的外侧需要补充$C(x,y,z,1)$的方块。 其次,在靠内的部分需要$4(x+y+z)$的方块。 所以$C(x,y,z,2)=C(x,y,z,1)+4(x+y+z)$ **第三层** 首先第一步和第二层的第一步相同,在最外侧需要补充$C(x,y,z,1)$的方块。 其次,由于比第二层多一圈,所以靠内的部分需要补充多一圈的$4(x+y+z)$,即为需要补充$2\times 4(x+y+z)$。 最后,还需要补充$4\times 1$个方块来填补在四个侧面。 所以$C(x,y,z,3)=C(x,y,z,1)+2\times 4(x+y+z)+1\times 4$ **第k层** 根据上述推理,可得: $$C(x,y,z,k)=2(xy+yz+xz)+(k-1)\times \left[ 4(x+y+z)+(k-2)\times 4 \right]$$

Code


public final class p126 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }	
	static final int LIMIT=200000;
	static public int C(int x,int y,int z,int k){
		return ((((k-1)*(x+y+z+k-2))<<1)+(x*y+y*z+x*z))<<1;
	}
	static public int c[]=new int[LIMIT+1];
    static public String run(){
		for(int x=1;C(x,x,x,1)<=LIMIT;x++)
			for(int y=x;C(x,y,y,1)<=LIMIT;y++)
				for(int z=y;C(x,y,z,1)<=LIMIT;z++)
					for(int k=1,ans;(ans=C(x,y,z,k))<=LIMIT;k++)
						c[ans]++;
		for(int i=0;i<=LIMIT;i++){
			if(c[i]==1000)
				return ""+i;
		}
		return null;
    }
}
18522
796ms