Run me!

Задание:

—— RunMe.py
import sys
sys.setrecursionlimit(99999)
def f(n):
    return n if n < 2 else f(n-2) + f(n-1)
print "SECCON{" + str(f(11011))[:32] + "}"
——

Очевидно, что для получения флага достаточно просто запустить представленный код … и уже через несколько недель (а возможно и месяцев) можно будет сдать флаг. Но, к сожалению, у нас не было столько времени, поэтому думаем, как бы оптимизировать. Попробуем найти какую-то закономерность. Вызовем функцию f() из задания от 10, 11, 12 и 13:

>>> def f(n):
    return n if n < 2 else f(n-2) + f(n-1)
>>> f(10)
55
>>> f(11)
89
>>> f(12)
144
>>> f(13)
233

Буквально сразу-же бросается в глаза, что f(13) = f(12) * 2 — f(10). Т.о. общая формула будет иметь вид: f(n) = f(n-1) * 2 — f(n-3). Это все, что нам необходимо для дальнейшей оптимизации кода:

def f(n):
    return n if n < 2 else f(n-2) + f(n-1)

d = {10:f(10), 11:f(11), 12:f(12)}

for i in range(13,11012):
    new_n = d[i-1]*2 - d[i-3]
    d[i] = new_n

print "SECCON{" + str(d[11011])[:32] + "}"

Флаг: SECCON{65076140832331717667772761541872}


Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *