Google Foobar: 解放兔子囚犯澄清

3

我正在完成谷歌的 Foobar 挑战,但是对于“释放兔子囚犯”这一关我感到非常困惑。我不需要代码,但我需要一些已经完成此题的人的见解。首先,看一下问题描述:

免费释放兔子囚犯
在Lambda指挥官的太空站爆炸之前,您需要释放兔子囚犯!不幸的是,指挥官对她最有价值的囚犯非常谨慎 - 它们都被分别关在最高安全级别的单独单元中。通过将钥匙放入每个控制台中,然后同时按下每个控制台上的打开按钮来打开单元格。当按下打开按钮时,每个钥匙会打开其对应的单元格上的锁。因此,所有控制台中的钥匙的并集必须是所有钥匙。该方案可能需要给不同手下派发多个副本的同一把钥匙。
由于每个控制台之间距离很远,因此需要一个单独的手下来操作每个控制台。幸运的是,您已经释放了一些兔子来帮助您,并且更好的是,当您担任Lambda指挥官的助手时,您能够偷走这些钥匙。问题是,您不知道哪些钥匙适用于哪些控制台。控制台被编程为知道每个手下都有哪些钥匙,以防止有人仅偷走所有钥匙并盲目使用它们。每个控制台都有标志,说明一些手下具有某些钥匙的数量。您怀疑Lambda指挥官有一种系统方法来决定要给每个手下哪些钥匙,以便他们可以使用控制台。
您需要找出Lambda指挥官用于分发钥匙的方案。您知道有多少手下拥有钥匙,以及每个单元格旁边有多少控制台。您知道Command Lambda不会发放比必需的钥匙更多的钥匙(超出键分配方案所需的范围),并且您需要与控制台数量相同的兔子携带钥匙才能打开单元格。
给定可用的兔子数量和打开单元格所需的锁数,请编写一个函数answer(num_buns,num_required),该函数返回如何分配钥匙的规范,以便任何num_required只要求能够打开锁的兔子都可以打开锁,但没有(num_required-1)只要求的兔子可以开锁。
每个锁从0开始编号。钥匙与其打开的锁的编号相同(因此对于重复的钥匙,数字将重复,因为它打开相同的锁)。对于给定的兔子,它们获取的钥匙表示为钥匙编号列表的排序。为了涵盖所有兔子,最终答案由每个单独兔子的钥匙列表的排序列表表示。找到字典序最小的密钥分配 - 即第一个兔子应从0开始连续拥有钥匙。
num_buns将始终介于1和9之间,num_required将始终介于0和9之间(两者均包括)。例如,如果您有3只兔子,并且仅需要其中1只打开单元格,则应该给每只兔子相同的钥匙,以便他们中的任何一只都能够打开它,如下所示:[[0],[0],[0]]如果您有2只兔子并且需要它们都打开
我无法理解为什么 `answer(5, 3) = [[0, 1, 2, 3, 4, 5], [0, 1, 2, 6, 7, 8], [0, 3, 4, 6, 7, 9], [1, 3, 5, 6, 8, 9], [2, 4, 5, 7, 8, 9]]`。在我看来, `[[0], [0, 1, 2], [0, 1, 2], [1], [2]]` 完全满足描述中的要求。我不知道为什么会有键的值大于 `num_required-1` 的情况。
我想到一种可能是所有随从 / 兔子需要拥有相同数量的钥匙,并且您只能拥有每个钥匙的 `num_required` 个。然而,如果这是情况,则 `[[0, 1, 2], [0, 1, 2], [0, 3, 4], [1, 3, 4], [2, 3, 4]]` 也可以。
接下来,我认为可能需要能够一次使用所有的 `num_required` 遥控器,而不管有多少台控制台。也就是说,你应该能够制作 `[6,7,8]` 和 `[0,1,2]`。但是,第一个兔子没有这些数字,这项要求就被打破了。
我卡住了。任何提示都将不胜感激!
1个回答

4
我认为你错过了它所说的部分:
但没有(num_required - 1)只兔子能组成一个团队。
我可以进一步解释我的解决方案,但那样会破坏乐趣。(我是那个 repo 的所有者)。让我们用你的答案来尝试一下。
[[0], [0, 1, 2], [0, 1, 2], [1], [2]]
你的控制台有3个。兔子2可以独立打开它,兔子3也可以独立打开它,但不符合规则。

1
{btsdaf} - Mark R
1
[[0,1,2,3,4,5],[0,1,2,3,8,9],[0,1,6,7,8,9],[2,3,4,5,6,7],[4,5,6,7,8,9]]为什么不可能是一个解决方案? - Kinjal Hinsu
基于此,显然以下列表并非有效解决方案: [[0, 1, 2, 3, 4, 5], [0, 1, 2, 6, 7, 8], [0, 3, 4, 6, 7, 9], [1, 3, 5, 6, 8, 9], [2, 4, 5, 7, 8, 9]] 因为兔子0可以独自打开它,兔子1也可以,以及其他许多仅由两只兔子组成的组合。 - Ross Patterson
但是在[[0, 1, 2, 3, 4, 5], [0, 1, 2, 6, 7, 8], [0, 3, 4, 6, 7, 9], [1, 3, 5, 6, 8, 9], [2, 4, 5, 7, 8, 9]]这个样例测试中,是否可以同时将bunny 0和bunny 1打开,因为它们都包含了0、1和2? - Circuit Planet

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接