0126 立方体层
* * * *
拉格朗日计划
* * * *
立方体层

要完全包住一个$3\times 2\times 1$的长方体表面,最少需要$22$个单位立方体。



若在此基础上再包裹一层,则需要46个单位立方体,而第三层需要78个单位立方体,第4层需要118个单位立方体。

同样地,要完全包住一个$5\times 1\times 1$的长方体表面也需要22个单位立方体,而要包住$5\times 3\times 1$或$7\times 2\times 1$或$11\times 1\times 1$的长方体表面,第一层就需要46个立方体。

记$C(n)$是在某一层中需要n个单位立方体的长方体总数,例如$C(22)=2$,$C(46)=4$,$C(78)=5$,$C(118)=8$。

可以验证154是第一个使$C(n)=10$的n。找出使得$C(n)=1000$的最小的n。

本题难度:



解答

令$f(a,b,c,k)$为$a\times b\times c$的长方体的第k层覆盖所需要的单位立方体数,则有 $$f(a,b,c,1)=2ab+2bc+2ac.$$ 该文中提供了$f(a,b,c,k)$的这样一种计算方式:把第k次覆盖所得的图形分别向前后左右上下移动一步,这六者的并集即第k+1次覆盖所得的图形,再由观察可得递推式 $$f(a,b,c,k)=f(a,b,c,k-1)+4(a+b+c)+8(k-2).$$ 直接递推得 $$f(a,b,c,k)=2(ab+bc+ac)+4(k-1)(a+b+c)+4(k-1)(k-2)=(a+b+c+2(k-1))^2-a^2-b^2-c^2-4(k-1).$$ 为$f(a,b,c,k)$选择一个合适的上界(以下使用的是20000),遍历$a,b,c,k$的所有可能组合(大约有三百万个)可得结果$18522$。

def f(a,b,c,d):
  return (a+b+c+2*(d-1))**2-a*a-b*b-c*c-4*(d-1)

target=20000

s=[0]*target

x=1
while f(x,x,x,1) < target:
  y=x
  while f(x,y,y,1) < target:
      z=y
      while f(x,y,z,1) < target:
          k=1
          while f(x,y,z,k) < target:
              s[f(x,y,z,k)]+=1
              k+=1
          z+=1
      y+=1
  x+=1

print min(z for z in range(target) if s[z]==1000)