问美食挑战:可爱的幸运羔羊

EN

''' Recursive form
Rules:
1) A0 = 1
2) An+1 !> 2*An
3) An-1 + An-2 !> An
4) n -> inf

Rewritten:
1) A0 = 1
2) An <= 2*An-1
3) An >= An-1 + An-2
4) n -> inf

Therefore:

A0 = 1, A-1 = 0, A-2 = 0
An-1 + An-2 <= An <= 2*An-1
'''


def maxPayout(LAMBs):
    '''
    Given An-1 + An-2 <= An <= 2*An-1
    An is maximized when An = 2*An-1
    '''
    # payouts[0] and payouts[1] exist as 'dummy' payouts
    payouts = [0, 0, 1]
    LAMBs -= payouts[-1]

    while (LAMBs >= 0):
        payouts.append(2*payouts[-1])
        LAMBs -= payouts[-1]

    # -2 for first two 'dummy' payouts and -1 for extra payout
    return len(payouts) - 2 - 1


def minPayout(LAMBs):
    '''
    Given An-1 + An-2 <= An <= 2*An-1
    An is minimized when An = An-1 + An-2
    '''
    # payouts[0] and payouts[1] exist as 'dummy' payouts
    payouts = [0, 0, 1]
    LAMBs -= payouts[-1]

    while (LAMBs >= 0):
        payouts.append(payouts[-1] + payouts[-2])
        LAMBs -= payouts[-1]

    # -2 for first two 'dummy' payouts and -1 for extra payout
    return len(payouts) - 2 - 1


def solution(total_lambs):
    return minPayout(total_lambs) - maxPayout(total_lambs)


def fastMaxPayout(LAMBs):
    '''
    Since maxPayout follows An = 2*An-1, maxPayout follows
    geometric sequence that can be reduced to exponential.

    An = 2^n

    Then we solve for sum(An = 2^n) <= LAMBs and the geometric
    series' sum formula follows:

    Sn = A0 * 1-r^n / (1-r)
    Sn = 1 * 1-2^n / (1-2)
    Sn = 2^n - 1

    Now we finally solve (Sn = 2^n - 1) <= LAMBs

    2^n <= LAMBs + 1
    n <= log2(LAMBs + 1)
    n = floor(log2(LAMBs + 1)) = (LAMBs + 1).bit_length() - 1
    '''
    return (LAMBs + 1).bit_length() - 1


def fastMinPayout(LAMBs):
    '''
    Since minPayout follows An = An-1 + An-2, minPayout follows
    a shifted Fibonnacci sequence. Apply Binet's formula to
    derive the nth Fibonnacci sequence.

    An-1 = Fn = ((1+sqrt(5) / 2)^n - (1-sqrt(5) / 2)^n) / sqrt(5)

    Substitute constants for variables to simplify

    let a = 1+sqrt(5) / 2
    let b = 1-sqrt(5) / 2
    let x = An-1 * sqrt(5)

    x = a^n - b^n
    a^n = x + b^n
    n = loga(x + b^n)ls

    And since lim n->inf b^n = 0, Binet's formula approximates:

    n = loga(x)

    Now we finally solve (Sn = An+2 - 1) >= LAMBs

    n+3 = loga(An+2 * sqrt(5)) = loga((An+2 - 1 + 1) * sqrt(5))
    n = loga((LAMBs + 1) * sqrt(5)) - 3
    '''
    from math import log, ceil, sqrt
    return int(ceil(log((LAMBs + 1 + 0.5)*sqrt(5), (1+sqrt(5)) / 2)) - 3)


def fastSolution(total_lambs):
    return fastMinPayout(total_lambs) - fastMaxPayout(total_lambs)


print(solution(143), fastSolution(143))