题目126：要遮盖一个立方型物体的每一个面需要多少个单位立方体？

欧拉计划

Cuboid layers

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.

题目：

要覆盖一个 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。

jerryxjr1220

1. '''
   
2. 每层需要覆盖的方块数：
   
3. Layers(x,y,z,n) = 2*(x*y+y*z+x*z)+4*(x+y+z+n-2)*(n-1)
   
4. '''
   
5. from itertools import count
   
6. from numba import jit
   
7. from functools import lru_cache
   
8. @lru_cache(maxsize=None)
   
9. @jit
   
10. def nCubics(x,y,z,n):
    
11.         return 2*(x*y+y*z+x*z)+4*(x+y+z+n-2)*(n-1)
    
12. 
    
13. def getMinNumberOfCuboids(C, maxN=20000):
    
14.     dCuboids = {}
    
15.     for w in count(1):
    
16.         num = nCubics(w, w, w, 1)
    
17.         if num > maxN: break            
    
18.         for h in count(w):
    
19.             num = nCubics(w, h, h, 1)
    
20.             if num > maxN: break            
    
21.             for d in count(h):
    
22.                 num = nCubics(w, h, d, 1)
    
23.                 if num > maxN: break
    
24.                 for l in count(2):
    
25.                     dCuboids[num] = dCuboids.get(num, 0) + 1
    
26.                     num = nCubics(w, h, d, l)
    
27.                     if num > maxN: break
    
28.     return min([key for key, value in dCuboids.items() if value == C])
    
29. print(getMinNumberOfCuboids(1000))

复制代码

18522
[Finished in 16.3s]