Назовём натуральное число интересным, если в его двоичной записи не более 2 единиц. Например, числа 4=100₂ и 40=101000₂ — интересные, а число 14=1110₂ интересным не является. Сколько существует интересных чисел, меньших 8000?

Для решения этой задачи можно воспользоваться методом динамического программирования.

Обозначим dp[i][j] - количество интересных чисел длины i, в которых ровно j единиц.

Имеем следующие рекуррентные соотношения: dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] dp[i][1] = dp[i-1][0] dp[i][2] = dp[i-1][1]

Начальные условия: dp[1][0] = 1 dp[1][1] = 1 dp[1][2] = 0

Теперь можем заполнить таблицу dp построчно, начиная с i=2 и заканчивая i=13 (так как 2^13 = 8192).

После заполнения таблицы dp[13][0] + dp[13][1] + dp[13][2] будет содержать количество интересных чисел, меньших 8000.

Подсчитаем эту сумму и получим ответ: 6096.