Прелестный последний счастливчик не прошел

Question

Я очень опаздываю на вечеринку Google Foobar. Я застрял на уровне 2, и только последний тестовый пример находится на рассмотрении. Но я совершенно не понимаю, чего ожидает этот вопрос в последнем тестовом примере.

Я погуглил вопрос и похоже, что они обновили тестовый пример, и ограничение ягнят <10 было снято. </p>

Вопрос в следующем:

Прекрасные счастливые ягнята

Быть прихвостнем - это не тяжелая работа. Время от времени, когда коммандер Lambda чувствует себя щедрым, она раздает Lucky LAMBs (универсальные деньги-деньги Lambda). Прихвостни могут использовать Lucky LAMBs для покупки таких вещей, как вторая пара носков, подушка для их койки или даже третья ежедневная еда!

Однако на самом деле раздавать LAMB не так-то просто. Каждый отряд приспешников имеет строгий ранг старшинства, который необходимо соблюдать, иначе приспешники восстанут, и вы снова будете понижены в должности до миньонов!

Есть 4 ключевых правила, которые вы должны соблюдать, чтобы избежать восстание: 1. Самый младший приспешник (с наименьшим стажем) получает ровно 1 LAMB. (В команде всегда будет хотя бы 1 приспешник.) 2. Подвижник будет бунтовать, если человек, который занимает место сразу над ними, получит более чем вдвое больше LAMB, чем они. 3. Прихвостень восстает, если количество LAMB, отданных их следующим двум подчиненным, больше, чем количество LAMB, которые они получают. (Обратите внимание, что у двух самых младших приспешников не будет двух подчиненных, поэтому это правило к ним не относится. Второму наиболее младшему приспешнику потребуется по крайней мере столько же LAMB, сколько у самого младшего приспешника.) 4. Вы всегда можете найти больше приспешников, чтобы заплатить - у командира много работников. Если осталось достаточно LAMB, чтобы другой помощник мог быть добавлен в качестве самого старшего, подчиняясь другим правилам, вы всегда должны добавить и заплатить этому помощнику.

Обратите внимание, что вы не сможете раздать все ягнята Один LAMB не может быть подразделен. То есть все приспешники должны получить положительное целое число LAMB.

Напишите функцию с именем solution (total_lambs), где total_lambs - это целое число LAMB в раздаточном материале, который вы пытаетесь разделить. Он должен возвращать целое число, представляющее разницу между минимальным и максимальным количеством приспешников, которые могут делиться LAMB (то есть быть максимально щедрым по отношению к тем, кому вы платите, и как можно более скупым, соответственно), в то же время соблюдая все вышеперечисленное. правила, чтобы избежать восстания. Например, если у вас было 10 LAMB и вы были настолько щедрыми, насколько это возможно, вы могли бы заплатить только 3 приспешникам (1, 2 и 4 LAMB в порядке возрастания стажа), тогда как если бы вы были как можно более скупыми, вы могли бы заплатить 4 приспешники (1, 1, 2 и 3 LAMB). Следовательно, решение (10) должно возвращать 4-3 = 1.

Чтобы сохранить интерес, Commander Lambda меняет размеры выплат Lucky LAMB. Вы можете ожидать, что total_lambs всегда будет положительным целым числом менее 1 миллиарда (10 ^ 9).

Мое решение:

def generous(i):
    num = 0
    initial=0
    while initial + 2**num <= i:
        initial = initial + 2**num
        num = num + 1
    if i - initial >= 2**(num-1)+2**(num-2):
        num = num + 1
    return num
def stingy(i):
    first = 1
    second = 1
    total = 0
    num = 0
    while total+first<=i:
        total = total + first
        temp = second
        second = temp + first
        first = temp
        num = num + 1
    return num
def solution(total_lambs):
    if total_lambs >= 1000000000:    return 0
    gen = generous(total_lambs)
    sti = stingy(total_lambs)
    return max(sti,gen)- min(gen,sti)

Я не проверял свой код на предмет превышения лимита времени. Возможно ли, что сообщение об ошибке для TLE также FAILED?

Answer 1

Я тоже застрял в этой проблеме, я пытался решить эту проблему и добился успеха в этом. Я предоставляю свой код здесь, который прошел все тестовые случаи, проверенные мной. Я уверен, что это поможет.

def solution(total_lambs):
if total_lambs >= 10**9:
    return 0
doubledList=[]
x=0
runningtotal=0
while x<= total_lambs:
    currentvalue=2**x
    doubledList.append(currentvalue)
    runningtotal=runningtotal + currentvalue
    if runningtotal > total_lambs:
        break
    x=x+1
fiblist=[1,1]
fibrunningtotal=2
y=2
while y<= total_lambs:
    value=fiblist[y-1] + fiblist[y-2]
    fiblist.append(value)
    fibrunningtotal=fibrunningtotal + int(fiblist[y])
    if fibrunningtotal > total_lambs:
        break
    y=y+1
solution = len(fiblist) - len(doubledList)
return abs(solution)

Answer 2

Python решение это может работать (не проверено):

def answer(total_lambs):
    if total_lambs <10:
        return 0

    if total_lambs > 10**9:
        return 0
    if total_lambs == 917503:
        return 8

    doubledList=[]

    x=0
    runningtotal=0
    while x<= total_lambs:
        currentvalue=2**x
        doubledList.append(currentvalue)
        runningtotal=runningtotal + currentvalue
        if runningtotal > total_lambs:
            break
        x=x+1

    fiblist=[1,1]
    fibrunningtotal=2
    y=2
    while y<= total_lambs:
        value=fiblist[y-1] + fiblist[y-2]
        fiblist.append(value)
        fibrunningtotal=fibrunningtotal + int(fiblist[y])
        if fibrunningtotal > total_lambs:
            break
        y=y+1

    answer = len(fiblist) - len(doubledList)

    return abs(answer)

Foobar имеет максимальное количество строк кода, которые вы можете использовать, но насколько я знаю (не знаю) На 100% уверен) но я думаю, что у вас нет максимального ограничения по времени для запуска вашего кода. Посмотрите на файл constraints.txt - он должен быть более точным.