python - 谷歌 foobar python : failure on two tests - lovely lucky lambs (counting of sequences)

Question

我受邀参加 Google 的 foobar 挑战赛。我目前处于 2.2 级，有以下问题。

可爱的幸运小羊

成为追随者并不全是苦差事。偶尔，当指挥官 Lambda 感到慷慨时，她会分发 Lucky LAMB(Lambda 的万能钱币)。追随者可以使用 Lucky LAMB 购买第二双 socks 、一个铺位枕头，甚至是每日第三顿饭!然而，实际分发 LAMB 并不容易。每个心腹小队都有严格的资历排名，必须遵守 - 否则心腹会造反，你们会再次降级为奴才!

为了避免反抗，您必须遵守 4 条关键规则:

1. The most junior henchman (with the least seniority) gets exactly 1 LAMB. (There will always be at least 1 henchman on a team.)
2. A henchman will revolt if the person who ranks immediately above them gets more than double the number of LAMBs they do.
3. A henchman will revolt if the amount of LAMBs given to their next two subordinates combined is more than the number of LAMBs they get. (Note that the two most junior henchmen won't have two subordinates, so this rule doesn't apply to them. The 2nd most junior henchman would require at least as many LAMBs as the most junior henchman.)
4. You can always find more henchmen to pay - the Commander has plenty of employees. If there are enough LAMBs left over such that another henchman could be added as the most senior while obeying the other rules, you must always add and pay that henchman.

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

编写一个名为 answer(total_lambs) 的函数，其中 total_lambs 是您要划分的讲义中 LAMB 的整数。它应该返回一个整数，表示可以分享 LAMB 的最小和最大追随者数量之间的差值(即，分别对你支付的人尽可能慷慨和尽可能吝啬)，同时仍然遵守上述所有条件避免叛乱的规则。

For instance, if you had 10 LAMBs and were as generous as possible, you could only pay 3 henchmen (1, 2, and 4 LAMBs, in order of ascending seniority), whereas if you were as stingy as possible, you could pay 4 henchmen (1, 1, 2, and 3 LAMBs). Therefore, answer(10) should return 4-3 = 1. To keep things interesting, Commander Lambda varies the sizes of the Lucky LAMB payouts: you can expect total_lambs to always be between 10 and 1 billion (10 ^ 9).

我的方法和代码

为了找到最少的追随者，必须慷慨地分发 LAMB，其具有几何级数 1,2,4,8...由于几何级数的总和由

( $S = 2^n -1$ 因此追随者的数量是 [ log_2 (S+1) ]

为了找到最大的追随者，必须以小气的方式给出 LAMB，顺序看起来是 fibbonaci 1 , 1, 2, 3, 5 ... 我们可以使用 Fibonacci 指数方法来获得最大追随者的数量:

遵循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)