Задание 16. Информатика. ЕГЭ. Поляков-4970

Минимальное значение функции \(F(n)\) равно \(8.\) Если число не кратно \(3,\) то просто отбрасывается последняя цифра в троичной записи этого числа, если же число делится на \(3,\) т.е. в троичной записи оно оканчивается на ноль, то к значению функции добавляется \(5.\) Т.о. функция \(F(n) = 18\) только для тех чисел, у которых в троичной записи присутствует ровно два нуля.

Python

Динамическое программирование

n = 100000000
tr = ""
while n > 0:
    tr = str(n % 3) + tr
    n //= 3

# Стартовое состояние
# Структура ключа: (zeros, is_less, is_started)
# zeros - количество значащий нулей
# is_less - было ли число меньше границы предыдущего состояния
# is_started - начали ли мы собирать "живые" числа
dp = {(0, 0, 0): 1}

# Идем по всем разрядам троичного числа
for c in tr:
    max_dig = int(c)
    next_dp = {}

    for (zeros, is_less, is_started), count in dp.items():
        # Определяем, какие цифры мы имеем право поставить в текущий разряд
        m = 2 if is_less else max_dig

        for d in range(m + 1):
            new_zeros = zeros + (1 if (d == 0 and is_started) else 0)
            new_is_less = is_less or (d < max_dig)
            new_is_started = is_started or (d > 0)

            state = (new_zeros, int(new_is_less), int(new_is_started))

            next_dp[state] = next_dp.get(state, 0) + count

    dp = next_dp

    # В конце собираем ответ: нам нужны состояния, где ровно 2 нуля и число началось
    # Флаг is_less может быть любым (0 или 1)
ans = dp.get((2, 0, 1), 0) + dp.get((2, 1, 1), 0)

print(ans)

Ответ: \(5201982\)