Решение №1

def build_bin(string, lenght):
    # Если длина построенного слова совпадает с максимальной длинной
    if len(string) == lenght:
        return string.count(’0’) == 3 and int(string, 2) <= 10**9
    counter = 0
    # Строим новые двоичные числа (прибавляем 0 или 1)
    if string.count(’0’) < 3:
        counter += build_bin(string + ’0’, lenght) + \
                   build_bin(string + ’1’, lenght)
    # Если дошли до количества равного 3, то прибавляем данное
    # число (дописываем единицы)
    if string.count(’0’) == 3:
        counter += int(string + ’1’ * (lenght - len(string)), 2) <= 10**9
    return counter

ans = 0
for i in range(4, 31):
    ans += build_bin(’1’, i)
print(ans)

Решение №2

ans = 0
# Будем строить вида "из всех единичек"
# Напимер: 1111111 и нужно перебрать три единички
# То есть вычесть 3 единички из двоичного числа
# Поэтому вычитаем степени двойки
for i in range(31):
    for j in range(i + 1, 31):
        for k in range(j + 1, 31):
            for a in range(k + 1, 31):
                N = 2 ** (a + 1)
                N -= 1
                N = N - 2 ** k - 2 ** j - 2 ** i
                if 1 <= N <= 10 ** 9:
                    ans += 1
print(ans)

Проанализируем, как изменяются значения на определенных значениях функции с помощью программы

def stepen(n):
    while n > 1:
        if n % 2 != 0:
            return False
        n //= 2
    return True

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

Заметим, что функция от степеней двойки выводит само число, а для остальных получается значение *степень двойки* + 2. И так до следующей степени двойки.

Число более того, Значит, что

Если число не будет полной степенью двойки, то при последовательном делении на мы вскоре получим нечетное число (кроме ) и вернем , вернут только степени двойки в данном диапазоне. Эффективно переберем все числа-степени двойки в данном отрезке

k = 0
x = 2
while x <= 100000000:
    k += 1
    x *= 2
print(k)

Заметим, что функция ищет манхэттенское расстояние в 3хмерном простанстве между точками и . Причем работает корректно только если .

Примечание: Манхеттенское расстояние, или расстояние городских кварталов - расстояние между двумя точками в n-мерном пространстве равное сумме модулей разностей их координат. Для 2хмерного пространства можно представить себе уличную планировку города Манхеттен, а именно квадратную сетку, где мы можем ходить только по этой сетке и расстояние между двумя ближайшими пересечениями равно единице.

Можем заметить, что сумма координат минус значение функции от этих координат всегда равно сумме координат точки, до которой мы ищём расстояние

Иными словами здесь инвариантом является .

Отсюда можем выразить

Ответ:

Поскольку числа слишком большие, то будем решать аналитикой. Для начала вычислим значения

Замечаем, что в общем виде вычисляется как

Вычислим требуемое и получим ответ.

Что такое Это есть просто число . А значит, нужно найти сумму чисел от 2 до 10000 включительно.

def f(n):
    if n == 0 or n == 1:
        return 1
    return f(n-1)*n

def C(n, k):
    if (k == 0 or k == n):
        return 1
    else:
        return C(n - 1, k - 1) + C(n - 1, k)


n, k = map(int, input().split())
print(C(n, k) * f(k))

def C(n, k):
    if (k == 0 or k == n):
        return 1
    else:
        return C(n - 1, k - 1) + C(n - 1, k)


n, k = map(int, input().split())
print(C(n, k))

Функция вычисляет факториал, т.е. произведение всех чисел от 1 до n.

То есть

Значит, после деления у нас останется только число 2023.

def f(n):
    if n == 1:
        return 1
    if n % 2 == 0:
        return f(n - 1)
    return f(n - 1) + n
print(f(10))

 

Если начать подставлять случайные и в функцию, то станет очевидно, что Значит нам нужно найти количество способов разложить число на произведение двух множителей. Тогда ответом будет количество делителей у числа так как для любого делителя найдется целое неотрицательное . Найдем все делители с помошью кода.

def get_divs(number):
    divs = []
    for i in range(1, int(number**0.5) + 1):
        if number % i == 0:
            divs.append(i)
            if i != int(number**0.5):
                divs.append(number//i)
    return divs

print(len(get_divs(5555555555555)))

Протестируем функцию на маленьких . Получим Оказалось, что функция рекурсивно находит

Заметим, что функция находит сумму чисел от до Тогда мы можем найти значение функции как Также заметим, что значение функции дает остаток по модулю только тогда, когда дает остаток по модулю и дает остаток в остальных случаях. Для поиска ответа нам нужно посчитать количество чисел с остатком на заданном промежутке. Тогда всего нам подходит числа.

Заметим, что функция на самом деле считает сумму цифр числа Значит нужно понять для каких сумма цифр числа больше суммы цифр числа Такое возможно только в случае перехода между разрядами, то есть нам подходят все принадлежащие промежутку и заканчивающиеся на Тогда нам подходит каждое десятое число, всего в промежутке чисел. Итого нам подходит чисел.

Напишем программу:

        def F(n):
            if n == 1 or n == 2 or n == 3:
                return 1
            if n > 3 and n % 2 == 0:
                return F(n - 1) + F(n - 3) + F(n // 3)
            if n > 3 and n % 2 != 0:
                return F(n - 2) + F(n - 1)

        print(F(30))

Напишем программу:

        def F(n):
            if n == 1:
                return 0
            if n == 2 or n == 3:
                return 1
            if n > 3:
                return F(n - 1) + n ** 2 + F(n - 2)

        print(F(19))

Заметим, что терминальными аргументами, то есть такими, что функции сразу же вернет ответ, являются числа делящиеся на . Поэтому достаточно лишь найти ближайшее больше либо равное первоначального аргумента такое значение. Для числа таковым является , а ответ 3.

Более того можно заметить, что

Ключевое замечание в этой задаче следующее: . Заметить это можно по-разному.

Первый способ: заметим что это значение дискретной производной многочлена , а значит так как , функция действительно для всех целых чисел в качестве результата возвращает .

Второй способ: давайте выведем первые значений функции и заметим закономерность. После этого докажем по индукции своё предположение.

    def f(a, x):
        if x == 1:
            return a
        if x % 2 != 0:
            return a * f(a, x - 1)
        b = f(a, x // 2)
        return b * b


    ans = 0
    for i in range(2, 10000 + 1):
        ans += f(i, i)
    print(ans % 10000)

  def f(n):
      if n == 1:
          return 1
      if n == 2:
          return 2
      return f(n - 1) * f(n - 2) * n

  print(f(5))