3034 КЕГЭ

#ПРЕДВАРИТЕЛЬНОЕ ОБЪЯСНЕНИЕ:
#Для всех чисел, F(n) минимум 6
#F(n) = 9 Для тех чисел, которые за прохождение функции были чётными и > 0 ровно три раза.
#Минимальным таким числом будет 2^3 степени, иначе просто 8.
#Струтура 8 будет 2*2*2.
#Но структура числа может быть и другой. Например (2*2+1)*2*2 (20)
#Разворачивая 20 мы будет иметь следующий ряд: 20 (деление на 2)-> 10 (деление на 2)-> 5 ( //2 )-> 2 (деление на 2)-> 1 ( //2 )-> 0
#Видим что мы делили на 2 (не целочисленно) только 3 раза. Значит для F(20) = 9
#Целочиселнное деление на 2 для нечётного числа n эквивалентно (n-1)/2
#Обратной операцией будет n*2 + 1. Для обычного деления на 2 эквивалентом будет n*2
#Когда мы целочисленно делим на 2 мы не меняем значение F(n).
#Значит число n, для которого F(n) = 9, на пути разворачивания 3 раза будет просто делиться на 2 и X раз целочисленно делится на 2
#Создавая число, для которого F(n) = 9, с помощью обратных операций, мы 3 раза просто умножим на 2, и X раз умножим на два и прибавим единицу
#Вопрос: зависит ли созданное число от порядка выполнения операций? Докажем, что да
#Возьмём два числа: 2*2*2*2 + 1 и (2*2*2+1)*2
#Это числа в которых мы каждую из операций применили одинаковое для обоих чисел количество раз, но в разном порядке
#Посчитав получим 17 и 18. Числа получились разные. Значит зависимость есть. НО!!!
#Для всех ли разных комбинаций из Z операций мы получим разные числа? Докажем, что да
#Операция *2 + 1, добавляет единицу, которая будет увеличиваться в 2 раза, с каждой следующей операцией
#Получается такая единица добавляет к итоговому числу 2^i, i - кол-во операций после прибавления этой единицы
#Чтобы числа не отличались, надо чтобы единицы добавили в сумме к итоговому число одинаковое число
#НО!!! 2^i > 2^(i-1) + 2^(i-2) + ... + 2^0 . Так как 2^(i-1) + 2^(i-2) + ... + 2^0 - сумма геометрической прогрессии
#2^(i-1) + 2^(i-2) + ... + 2^0 = (2^i - 1)/(1) = 2^i - 1
#И очевидно, что 2^i > 2^i - 1
#А если 2^(i-1) + 2^(i-2) + ... + 2^0, значит что единицу, которую прибавили на хотя бы на одну операцию раньше, не получится
#набрать суммой единиц, которые добавили позже. Значит не получится составить одно и тоже число разными комбинациями,
#так как если в одной из комбинации хотя бы одна операция *2+1 идёт раньше чем в другой,
#то число, полученное этой комбинацией будет больше чем в другой
#Значит количество N разных чисел, которые составлены из Z разных комбинаций операций, где Z = 3 + X, будет равно количество перестановок
#3 "*2" операций и X "*2 + 1" операций. Значит N = (3+X)! / (3! * X!) (формула перестановок без повторений)
#НО!!! Может быть так, что число, полученное нами, будет больше 1 000 000 000. А такие нам не подходят
#Очевидно, что используя Z операций, мы получим наибольшее число, если все операции *2 + 1 поставим в начале.
#А минимальное, если поставим в конце.
#Найдём максимальное Z, при котором максимальное число <= 1 000 000 000

maxStableZ = -1

for Z in range(3, 1000):
    n = 1

    for j in range(Z-3):
        n = n*2 + 1

    n = n * 2**3

    if n > 1_000_000_000:
        maxStableZ = Z - 1
        break


#Найдём максимальное Z при котором минимальное число будет <=  1 000 000 000

maxZ = -1

for Z in range(3, 1000):
    n = 2**3

    for j in range(Z-3):
        n = n*2 + 1

    if n > 1_000_000_000:
        maxZ = Z - 1
        break

#для Z <= maxStableZ, все числа из Z операций будут <= 1 000 000 000
#поэтому просто посчитаем количество перестановок из Z in range(3, maxStableZ + 1) операций

import math

c = 0

for Z in range(3, maxStableZ + 1):
    c += math.factorial(Z)/(math.factorial(3)*math.factorial(Z-3))

#для Z, где maxStableZ < Z <= maxZ , каждое составленное нами число придётся рассматривать отдельно

for i1 in range(0, maxZ):
    for i2 in range(i1+1, maxZ):
        for i3 in range(i2+1, maxZ):
            a = [0] * maxZ
            a[i1] = 1
            a[i2] = 1
            a[i3] = 1
            n = 1
            for j in a:
                if j == 1:
                    n = n * 2
                else:
                    n = n * 2 + 1

            if n <= 1_000_000_000:
                c += 1

print(c)