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

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

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

Изначально у нас есть два интересных числа длиной 1 бит: 0 и 1. Поэтому dp[1][0] = 1, dp[1][1] = 1.

Теперь можем заполнить таблицу dp по формуле выше и найти количество интересных чисел длиной не более 12 бит, так как 2^12 = 4096.

После этого просуммируем все значения dp[i][j] для i от 1 до 12 и j от 0 до 2, чтобы найти количество интересных чисел меньше 4000.

Решив данную задачу, получим, что существует 2047 интересных чисел, меньших 4000.