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

Для решения этой задачи можно воспользоваться методом динамического программирования. Обозначим dp[i][j] как количество интересных чисел длиной i бит, содержащих j единиц. Тогда dp[i][j] = dp[i-1][j] + dp[i-1][j-1].

Изначально у нас есть одно интересное число длиной 1 бит (0) и одно интересное число длиной 1 бит, содержащее одну единицу (1). Далее, используя формулу dp[i][j] = dp[i-1][j] + dp[i-1][j-1], мы можем построить все интересные числа длиной до 13 бит включительно.

Для каждой длины числа i от 1 до 13 и для каждого количества единиц j от 0 до 2 мы можем посчитать количество интересных чисел dp[i][j]. Затем просуммируем все dp[13][j] для j от 0 до 2, чтобы получить общее количество интересных чисел длиной до 13 бит включительно.

Теперь остаётся проверить, сколько из этих чисел меньше 8000. В итоге мы получим количество интересных чисел, меньших 8000.