题目126：要遮盖一个立方型物体的每一个面需要多少个单位立方体？
Cuboid layersThe 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.
题目：
要覆盖一个 3 x 2 x 1 的立方体的每一个外露面，至少需要 22 个单位立方体。
如果我们给这个立方形物体再覆盖上第二层，那么覆盖这个新立方形物体的每个外露面需要 46 个单位立方体；第三层则需要 78 个单位立方体；第四个立方体需要 118 个单位立方体。
但是，如果第一层的大小是 5 x 1 x 1 的话，覆盖第一层同样需要 22 个单位立方体；类似的，覆盖大小为 5 x 3 x 1, 7 x 2 x 1, 和 11 x 1 x 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。
'''
每层需要覆盖的方块数：
Layers(x,y,z,n) = 2*(x*y+y*z+x*z)+4*(x+y+z+n-2)*(n-1)
'''
from itertools import count
from numba import jit
from functools import lru_cache
@lru_cache(maxsize=None)
@jit
def nCubics(x,y,z,n):
return 2*(x*y+y*z+x*z)+4*(x+y+z+n-2)*(n-1)
def getMinNumberOfCuboids(C, maxN=20000):
dCuboids = {}
for w in count(1):
num = nCubics(w, w, w, 1)
if num > maxN: break
for h in count(w):
num = nCubics(w, h, h, 1)
if num > maxN: break
for d in count(h):
num = nCubics(w, h, d, 1)
if num > maxN: break
for l in count(2):
dCuboids = dCuboids.get(num, 0) + 1
num = nCubics(w, h, d, l)
if num > maxN: break
return min()
print(getMinNumberOfCuboids(1000))
18522
页:
[1]