Ваш конспект

Оптимизация решения 16-го задания ЕГЭ по информатике

Ключевые тезисы:

• Классическое решение через setrecursionlimit() ненадёжно на ЕГЭ
• Использование LRU_cache с разумным лимитом (100) — оптимальный подход
• Для задач с очень большими числами нужно сохранять только ключевые значения
• В задачах с двумя функциями важен порядок вычислений
• Предварительный разогрев функций от граничных значений обязателен

Проблема стандартного решения

При классической рекурсии с большими числами (например, f(247563)) возникает две проблемы:

1. Превышение глубины рекурсии (стандартный лимит Python — 1000 вызовов)
2. Переполнение оперативной памяти при кэшировании огромных промежуточных значений

Ненадёжные решения:

• setrecursionlimit() — зависит от мощности компьютера, на ЕГЭ может не сработать
• @lru_cache без ограничений (maxsize=None) — может "убить" компьютер из-за переполнения памяти

Оптимальное решение: LRU_cache с лимитом

Используем декоратор @lru_cache(maxsize=100):

from functools import lru_cache

@lru_cache(maxsize=100)
def f(n):
    if n < 10:
        return 1
    return n + 3 * f(n - 3)

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

Запоминание ключевых значений

Если в задаче требуются значения функции для конкретных больших чисел (например, f(247563), f(247560), f(247557)), их нужно сохранять отдельно:

x1 = x2 = x3 = 0
for n in range(10, max(247563, 247560, 247557) + 1):
    if n == 247563:
        x1 = f(n)
    elif n == 247560:
        x2 = f(n)
    elif n == 247557:
        x3 = f(n)
    else:
        f(n)  # просто прогреваем кэш

print(x1 // x2 // x3)  # Используем сохранённые значения

Преимущество: Мы храним в памяти только 100 последних вычисленных значений и 3 ключевых числа, а не сотни тысяч.

Задачи с двумя функциями

Пример задачи:

@lru_cache(maxsize=100)
def f(n):
    if n > 128:
        return f(n - 5) + 1092
    return 5 * g(n - 7) + 29

@lru_cache(maxsize=100)
def g(n):
    if n > 303728:
        return n - 15
    return g(n + 8) // 2

Алгоритм решения:

1. Анализируем вызовы: Смотрим, какая функция запрашивается в print() (в примере — f(2049))
2. Определяем порядок прогрева: Чтобы вычислить f(128), потребуется g(114), а для g(114) нужны вычисления от границы 303728 вниз
3. Сначала прогреваем g(): Вызываем g(n) от её границы (303728) до минимального требуемого значения (например, 114) с шагом -1
4. Затем прогреваем f(): Вызываем f(n) от её границы (128) до требуемого значения (2049)
5. Выводим результат: print(f(2049))

Важно: Порядок прогрева критичен! Если начать с f(), рекурсия уйдёт в g() с большим числом и превысит глубину.

Чего избегать

• setrecursionlimit() — ненадёжно, зависит от железа
• @lru_cache(maxsize=None) — опасно, может переполнить память
• Решение "в лоб" без анализа зависимостей функций — приведёт к ошибке

Итоговая стратегия

1. Всегда используем @lru_cache(maxsize=100)
2. Для задач с одним вызовом — прогреваем функцию от граничного значения до нужного, сохраняя ключевые точки
3. Для задач с двумя функциями — анализируем зависимости и прогреваем в правильном порядке (сначала вложенную)
4. Тестируем на небольших значениях перед запуском на больших

Вывод: Шестнадцатое задание решается не силой, а умом. Правильная стратегия кэширования и порядок вычислений гарантируют балл без риска "убить" компьютер на экзамене.