Question

Назовём красивыми числа, в записи которых есть цифры, отличающиеся друг от друга ровно на единицу (например: 12, 265, 3047). Сумма красивых чисел, меньших 30, равна 45 (10 + 12 + 23 = 45). Найдите сумму красивых натуральных чисел, меньших 10000.

Answer 1

...сумма = 33.086.416

Answer 2

Для решения этой задачи мы можем использовать алгоритм динамического программирования. Создадим массив dp, где dp[i] будет содержать сумму всех красивых чисел, меньших i.

Начальное условие: dp[0] = 0 (нет красивых чисел меньше 0).

Затем мы будем заполнять массив dp по порядку от 1 до 9999, используя следующее рекуррентное соотношение:

dp[i] = dp[i-1] + dp[i-2], если последняя цифра числа i равна последней цифре числа i-1 + 1, иначе dp[i] = dp[i-1].

То есть, если последние цифры чисел i и i-1 отличаются на единицу, то мы можем добавить i к сумме красивых чисел, меньших i-1. В противном случае, мы просто копируем сумму из dp[i-1].

После заполнения массива dp, сумма всех красивых чисел, меньших 10000, будет равна dp[9999].

Приведённый ниже код на языке Python реализует этот алгоритм:

pythonCopy code
dp = [0] * 10000
dp[0] = 0

for i in range(1, 10000):
    if i < 10:
        dp[i] = dp[i-1] + 1
    else:
        last_digit = i % 10
        second_last_digit = (i // 10) % 10

        if abs(last_digit - second_last_digit) == 1:
            dp[i] = dp[i-1] + dp[i-2]
        else:
            dp[i] = dp[i-1]

beautiful_sum = sum(dp[:10000])
print(beautiful_sum)

Запустив этот код, мы получим сумму красивых натуральных чисел, меньших 10000.