090. 立方体数字对(Cube digit pairs)

在一个立方体的六个面上分别标上不同的数字(从0到9),另一个立方体也一样。将这两个立方体按不同的方向并排摆放,我们可以得到各种各样的两位数。例如,平方数64可以通过这样摆放获得:

img

事实上,通过仔细地选择两个立方体上的数字,我们可以摆放出所有小于\(100\)的平方数:\(01,04,09,16,25,36,49,64,81\)。例如,其中一种方式就是在一个立方体上标上{0, 5, 6, 7, 8, 9},在另一个立方体上标上{1, 2, 3, 4, 8, 9}。然而,对于 {0, 5, 6, 7, 8, 9}和{1, 2, 3, 4, 6, 7}这种情况,我们需要允许数字6或9可以颠倒过来,否则就不可能组成平方数09了。

在考虑什么是不同的标法时,我们关注的是立方体上有哪些数字,而不关心它们的顺序,因此:

  • {1, 2, 3, 4, 5, 6}等价于{3, 6, 4, 1, 2, 5}
  • {1, 2, 3, 4, 5, 6}不同于{1, 2, 3, 4, 5, 9}

但因为我们允许在摆放两位数时将6和9颠倒过来互相表示,这个例子中的两个不同的集合都可以代表拓展集{1, 2, 3, 4, 5, 6, 9}。

对这两个立方体有多少中不同的标法可以摆放出所有的平方数?

分析:很奇怪这道题的难度系统竟然为40%,但实际上只是一道比较简单的排列组合问题。需要特别关注的问题是我们允许6和9相互颠倒过来表示,所以为了处理的方便,我们可以把所有的9都看作是颠倒过来的6,例如我们可以把平方数9写成6、49写成46。

我们可以使用\(python\)自带的\(itertools\)中的\(combinations\)函数从0至9十个数字中选出六个,需要注意的是因为我们把9当作提颠倒的6,所以我们也会把9替换成6,所以最终这十个数字中没有9,但有两个6。在选择出这些数形成组合后,我们对每一对组合,也就是两个立方体的数字集合,计算它们可以形成的所有数字,然后看这些数字是否包含了全部一百以内的平方数,这个判断可以使用\(python\)中集合判断包含关系的操作符。如果全部一百以内的平方数构成全部可形成数字的子集,则是一个满足题目要求的解,可以把计数增加一。

在计算出最终的计数以后,由于所有组合中有一半组合是有交换立方体一和立方体二的顺序形成的,不构成独特的解,所以在最终计数上还需要再除以二,即为题目所求。代码如下:

# timec cost = 456 ms ± 2.91 ms

from itertools import combinations

def main():
    counter = 0
    sq = {1,4,6,16,25,36,46,64,81}
    cube_number = list(range(9)) + [6]
    comb = list(combinations(cube_number,6))
    for i in comb:
        for j in comb:
            numbers = {e for x in i for y in j for e in (10*x+y,10*y+x)}
            if sq <= numbers:
                counter += 1
    return counter//2