Google foobar python：两项测试均失败-可爱的幸运羔羊（序列计数）

Question

我受邀参加Google的foobar挑战赛。我目前在2.2级时遇到以下问题。

可爱的幸运羔羊

做一个小伙子并不单单是苦力。有时，当Lambda指挥官感到慷慨时，她会分发Lucky LAMBs（Lambda的多用途钱袋）。武装分子可以使用幸运的羔羊来买东西，例如第二双袜子，铺床上的枕头，甚至是第三顿日常餐！但是，要传播出LAMB并不容易。每个小伙子都有严格的资历等级，必须予以尊重-否则小伙子将起义，而你们所有人都将再次被降级为奴才！

为避免起义，必须遵循4条关键规则：

1. 最年轻的小伙子（资历最少）刚好得到1个LAMB。（一个团队中总是至少有1个随从。）
2. 如果紧随其后的人获得的LAMB数量增加一倍以上，那将成为反叛者。
3. 如果向其下两个下属提供的LAMB数量超过其获得的LAMB数量，则该弓箭手将起义。（请注意，两个最初级的he夫不会有两个下属，因此此规则不适用于他们。第二个最初级的he夫至少需要与最初级的he夫一样多的LAMB。）
4. 您总能找到更多要支付的he夫-司令官有大量员工。如果有足够的LAMB剩余，可以在遵守其他规则的同时将另一名行政长官添加为最高级，则您必须始终添加该名警官并向其付款。

请注意，您可能无法分发所有LAMB。单个LAMB不能再细分。也就是说，所有的追随者必须获得正整数的LAMB。

编写一个名为answer（total_lambs）的函数，其中total_lambs是您要除法的讲义中LAMB的整数。它应该返回一个整数，该整数表示可以共享LAMB的小伙子们的最小数量和最大数量之间的差额（即，分别对您所支付的人尽可能慷慨和尽可能小气），同时仍然要遵守上述所有条件避免起义的规则。

例如，如果您有10个LAMB，并且尽可能地慷慨，则您只能支付3名追随者（按升序排列，分别有1、2和4名LAMB），而如果您太小气，则可以支付4追随者（1、2、3和3个小羊）。因此，answer（10）应该返回4-3 =1。为使事情变得有趣，Commander Lambda更改了幸运LAMB支出的大小：您可以期望total_lambs始终在10到10亿之间（10 ^ 9）。

我的方法和代码

为了找到最低限度的血统，必须慷慨地给予LAMB，其几何级数为 1,2,4,8 ...由于几何级数的总和为

（$ S = 2 ^ n -1 $，因此，追随者的人数为[log_2（S + 1）]

要找到最大的帮手，必须以小气的方式给出LAMB，以使他们看起来像斐波那契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个测试用例（Google不会告诉您详细信息）。该代码通过了其中的8个，最后两个失败。我不确定这里是否缺少边缘案例。任何帮助/建议，我们将不胜感激。谢谢！！

Answer 1

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)