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

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

Теперь можем заполнить таблицу dp[i][j] для всех i от 1 до 11 и j от 0 до 2. После этого просуммируем все значения dp[i][j] для i от 1 до 11 и j от 0 до 2, которые меньше 2000. Получим ответ: 2047.

Итак, существует 2047 интересных чисел, меньших 2000.