时间戳

首页 > 解决方案 > 如何以 +-2 的边距或误差获得正确数量的不同组合锁？

python - 如何以 +-2 的边距或误差获得正确数量的不同组合锁？

问题描述

我正在尝试解决 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。我不太确定为什么会发生这种情况。我添加数组仅用于显示目的。任何帮助将不胜感激！

标签： pythonarraysfunctionloops

解决方案

You're going to a lot of trouble to solve this by brute force.

First of all, your two check routines have identical functionality: just call the same routine for both combinations, giving the correct combination as a second set of parameters.

The critical logic problem is handling the dial wrap-around: you miss picking up the adjacent numbers. Run 49 through your check against a correct value of 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.

Instead, you can check each end of the dial:

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

Another way is to start by making a list of acceptable values:

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

... but note that you have to change the 0 value to dial. For instance, for a value of 1, you want a list of [49, 50, 1, 2, 3]

With this done, you can check like this:

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

If you want to upgrade to the itertools package, you can simply generate all desired combinations:

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

Do that for both given combinations and take the union of the two sets. The length of the union is the desired answer.

I see the follow-up isn't obvious -- at least, it's not appearing in the comments.

  • You have 5*5*5 solutions for each combination; start with 250 as your total.
  • Compute the sizes of the overlap sets: the numbers in each triple that can serve for each combination. For your given problem, those are [3],[4],[5]
  • The product of those set sizes is the quantity of overlap: 1*1*1 in this case.
  • The overlapping solutions got double-counted, so simply subtract the extra from 250, giving the answer of 249.

For example, given 1-2-3 and 49-6-6, you would get sets

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

The sizes are 3, 1, 2; the product of those numbers is 6, so your answer is 250-6 = 244

Final note: If you're careful with your modular arithmetic, you can directly compute the set sizes without building the sets, making the program very short.

推荐阅读