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

Question

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

可爱的幸运小羊

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

为了避免叛乱，您必须遵守 4 条关键规则：

The most junior henchman (with the least seniority) gets exactly 1 LAMB. (There will always be at least 1 henchman on a team.)

A henchman will revolt if the person who ranks immediately above them gets more than double the number of LAMBs they do.

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.)

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 的整数。它应该 return 一个整数，表示可以分享 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) ]

为了找到最大的追随者，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个测试用例（Google不告诉你细节）。此代码通过了其中的 8 个，但在最后两个上失败了。我不确定这里是否存在我遗漏的边缘情况。非常感谢任何help/suggestion。谢谢！！

Answer 1

测试 9 检查类似 answer(13) 的案例。在这种情况下，min_hunchmen = 4，而不是 3。几何序列表示您支付给第四名追随者 8 美元，如果 total_lambs = 13，这是不可能的，但是您可以支付给第四名追随者 6 美元，而不是打破任何规则。

额外检查一下剩余现金是否多于支付给最后两个心腹的款项将解决这个问题。

希望这对您有所帮助，如果您知道如何通过测试 #10，请随时分享:)

Answer 2

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)

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

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

python

algorithm

big-o

fibonacci

python-2.7