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.

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