谷歌的foobar挑战：Python两个测试失败 - 可爱的幸运羊（序列计数）

Question

谷歌的foobar挑战：Python两个测试失败 - 可爱的幸运羊（序列计数）

5

我被邀请参加谷歌的Foobar挑战，目前正在2.2级别上遇到以下问题。

可爱的幸运小羊

当一个手下遇到困境时，并不是所有工作都很繁琐。偶尔当Lambda指挥官感到慷慨时，她会派发一些幸运小羊（Lambda万能货币）。手下们可以使用这些幸运小羊来购买像第二双袜子、铺垫或甚至第三顿饭之类的东西！然而，实际分发幸运小羊并不容易。每个手下小队都有严格的资历等级制度必须得到尊重--否则，手下将反抗，而你们所有人都将被降级成为奴才！

要避免发生反抗，必须遵循以下4个关键规则：

最年轻的手下（资历最低）得到1只LAMB。（一个团队中至少有1个手下。）

如果排名紧随其后的人得到比他们多两倍的LAMB，则手下将反抗。

如果给予他们接下来的任意两个下属的LAMB的总数大于他们自己的数量，则手下将反抗。（请注意，最年轻的两个手下没有2个下属，因此这个规则不适用于他们。第二年轻的手下需要至少与最年轻的手下一样多的LAMB。）

你可以随时找到更多的手下来支付——指挥官有足够的雇员。如果剩余的LAMB足够添加另一个资历最高的手下，并遵守其他规则，则必须始终添加并支付那个手下。

请注意，您可能无法分配所有的LAMB。单个的LAMB不能再细分了。也就是说，所有手下都必须得到正整数数量的LAMB。

编写一个名为answer（total_lambs）的函数，其中total_lambs是您正在尝试分发的LAMB的整数数量。它应该返回一个整数，表示在仍然遵守上述所有规则以避免反抗的情况下，可以分享LAMB的手下的最小和最大人数之间的差异，一方面要慷慨地支付，另一方面要吝啬。

例如，如果你有10只LAMB并且非常慷慨，你只能支付3名走狗（按升序排序为1、2和4 LAMBs），而如果你非常吝啬，你可以支付4名走狗（1、1、2和3 LAMBs）。因此，answer（10）应该返回4-3=1。为了保持趣味性，Lambda指挥官改变了幸运LAMB支付的大小：你可以期望总量在10亿（10^9）和10之间。 我的方法和代码 为了找到最小的走狗，必须慷慨地分发LAMBs，这是一种几何级数 1,2,4,8... 因为几何级数的总和为( $S = 2^n -1$)所以走狗的数量是[ log_2 (S+1) ]。

要找到最大的走狗，必须以吝啬的方式分发LAMBs，这似乎是斐波那契数列1, 1, 2, 3, 5... 我们可以使用斐波那契索引方法来获得最大的走狗数：

以下是Python代码：

from math import sqrt
from math import log
from math import pow

def answer(total_lambs):
    phi = (1+sqrt(5))/2  # golden search ratio
    tau = (1-sqrt(5))/2  # equal to 1/phi
    eps = pow(10, -10)

    max_hunchmen = int(round(log((total_lambs + 1) * sqrt(5)+eps, phi))) - 2
    Fib_num = int(round((pow(phi, max_hunchmen+2)-pow(tau,max_hunchmen+2))/sqrt(5)))
    if total_lambs+1 < Fib_num:
      max_hunchmen -= 1

    min_hunchmen = int(log((total_lambs + 1), 2))

    return abs(max_hunchmen - min_hunchmen)

有10个测试用例（谷歌没有告诉你细节）。这段代码通过了其中8个，但在最后两个测试用例上失败了。我不确定是否有我遗漏的边缘情况。非常感谢任何帮助/建议。谢谢！

- gvavvari

1

令人惊讶的是，我未能通过另一组两个测试用例。我未能通过第6和第7个案例。对于将来查看此内容的任何人，请做出（错误的）假设，即您不能恰好支付最后一个打手与倒数第二个和倒数第三个之和相等。这基本上意味着在您的代码中将“> =”符号更改为“>”符号。我知道这是错误的，但我认为谷歌的测试用例有缺陷。 - vikarjramun

2个回答

4

测试9检查类似于answer（13）的情况。在这种情况下，min_hunchmen = 4而不是3。几何序列表示您要支付第四个手下八美元，这在total_lambs = 13的情况下是不可能的，但是您可以支付第四个手下6美元而不违反任何规则。

额外的检查以确保剩余现金大于最后两个手下的支付将解决此问题。

希望这有所帮助，如果您找到了通过测试＃10的方法，请随时分享：）

- vnuno

1

谢谢！这解决了第9个测试用例的问题——添加了一个检查，确保剩余的现金可以给另一个最高级别的手下。 - gvavvari

@gvavvari 你是如何做到的？ - Serhii Matrunchyk

测试用例10对我仍然不起作用。有什么建议吗？ - Sudarshan Sunder

@SudarshanSunder，如果total_lambs不符合限制条件，即输入不符合给定的限制条件，请返回0。 - Pbd

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Quantum · Accepted Answer

phi = (1+sqrt(5))/2  
tau = (1-sqrt(5))/2  
eps = pow(10, -10)

max_hunchmen = int(round(log((total_lambs + 1) * sqrt(5)+eps, phi))) - 2
Fib_num = int(round((pow(phi, max_hunchmen+2)-pow(tau,max_hunchmen+2))/sqrt(5)))
if total_lambs+1 < Fib_num:
  max_hunchmen -= 1
elif total_lambs + 1 == Fib_num:
    total_lambs = Fib_num
if (total_lambs + 1) % 2 == 0:
     min_hunchmen = int(round(log((total_lambs + 1), 2)))
else:
    min_hunchmen = int(log((total_lambs + 1), 2))

return abs(max_hunchmen - min_hunchmen)