python - 如何获得正确数量的不同密码锁且边际或误差为+-2？

Question

我正在尝试解决 usaco 密码锁问题，其中为您提供了两个锁组合。这些锁的误差范围为 +- 2，因此如果您有一把 1-3-5 的密码锁，则 3-1-7 的密码仍然可以解决它。

您还会获得一个拨号盘。例如，拨号从 1 开始，到给定数字结束。因此，如果拨号盘为 50，则它将从 1 开始，到 50 结束。由于拨号盘的开头与拨号盘的结尾相邻，因此密码 49-1-3 也可以解决 1-3- 的密码锁。 5.

在此程序中，您必须输出两个锁组合的不同解决方案的数量。根据记录，组合 3-2-1 和 1-2-3 被认为是不同的，但组合 2-2-2 和 2-2-2 则不是。

我尝试创建两个函数，一个用于检查三个数字是否与第一个组合锁的约束匹配，另一个用于检查三个数字是否与第二个组合锁的约束匹配。

a,b,c = 1,2,3
d,e,f = 5,6,7
dial = 50

def check(i,j,k):
    i = (i+dial) % dial
    j = (j+dial) % dial
    k = (k+dial) % dial
    if abs(a-i) <= 2 and abs(b-j) <= 2 and abs(c-k) <= 2:
        return True
    return False

def check1(i,j,k):
    i = (i+dial) % dial
    j = (j+dial) % dial
    k = (k+dial) % dial
    if abs(d-i) <= 2 and abs(e-j) <= 2 and abs(f-k) <= 2:
        return True
    return False

res = []
count = 0
for i in range(1,dial+1):
    for j in range(1,dial+1):
        for k in range(1,dial+1):
            if check(i,j,k):
                count += 1
                res.append([i,j,k])
            if check1(i,j,k):
                count += 1
                res.append([i,j,k])

print(sorted(res))
print(count)

表盘为 50，第一个组合为 1-2-3，第二个组合为 5-6-7。

程序应该输出 249 作为计数，但它却输出 225。我不太确定为什么会发生这种情况。我添加的数组仅用于显示目的。任何帮助将不胜感激!

Answer 1

通过暴力解决这个问题会很麻烦。

首先，您的两个检查例程具有相同的功能:只需为两种组合调用相同的例程，并给出正确的组合作为第二组参数。

关键的逻辑问题是处理拨号环绕:您错过了相邻的号码。运行 49 通过检查 1 的正确值:

# using a=1, i=49
i = (1+50)%50   # i = 1
...
if abs(1-49) <= 2 ...   # abs(1-49) is 48.  You need it to show up as 2.

相反，您可以检查表盘的每一端:

a_diff = abs(i-a)
if a_diff <=2 or a_diff >= (dial-2) ...

另一种方法是首先列出可接受的值:

a_vals = [(a-oops) % dial] for oops in range(-2, 3)]

...但请注意，您必须将 0 值更改为 dial。例如，对于 1 的值，您需要一个 [49, 50, 1, 2, 3]

的列表

完成此操作后，您可以像这样检查:

if i in a_vals and j in b_vals and k in c_vals:
    ...

<小时/>

如果您想升级到 itertools 软件包，您可以简单地生成所有所需的组合:

combo = set(itertools.product(a_list, b_list_c_list) )

对两个给定的组合执行此操作，并取两个集合的并集。联合的长度就是所需的答案。

<小时/>

我发现后续行动并不明显——至少，它没有出现在评论中。

• 每个组合都有 5*5*5 个解决方案；从 250 作为您的总数开始。
• 计算重叠集的大小:每个三元组中可用于每个组合的数字。对于您给定的问题，这些是 [3],[4],[5]
• 这些集合大小的乘积就是重叠数量:在本例中为 1*1*1。
• 重叠的解被重复计算，因此只需从 250 中减去多余的部分，得到答案 249。

例如，给定 1-2-3 和 49-6-6，您将获得集合

{49, 50, 1}
{4}
{4, 5}

尺寸为 3、1、2；这些数字的乘积是 6，所以您的答案是 250-6 = 244

最后一点:如果您对模运算非常小心，您可以直接计算集合大小而无需构建集合，从而使程序非常简短。