Как много открытий можно сделать, исследуя числа и составляющие их цифры!

Петя очень любит арифметику, и кроме домашних заданий он постоянно придумывает дополнительные задачи. Однажды он стал прибавлять к натуральным числам сумму составляющих их цифр. Петя обнаружил, что некоторые числа, например 20, не могут быть получены из других чисел в результате такого действия. Эти числа ему не понравились, и он назвал их некрасивыми.

Позже, когда Петя начал изучать информатику, те же исследования он стал проводить с натуральными числами в двоичной системе счисления. Например, двоичное число 1110­₂ (в десятичной системе — 14) можно получить из числа 1100₂ (в десятичной системе — 12), прибавив к последнему сумму его цифр:

1100₂ + 10₂ = 1110₂.

Петя решил исследовать множество двоичных некрасивых чисел. Первые пять некрасивых чисел он нашел без труда: 1 = 1₂, 4 = 100₂, 6 = 110₂, 13 = 1101₂, 15 = 1111₂. Продолжить работу он собирается с помощью компьютера.

Требуется написать программу, которая определяет количество двоичных некрасивых чисел, не превосходящих заданного числа n.

В стране Флатландия решили построить легкоатлетический манеж с M одинаковыми прямолинейными беговыми дорожками. Они будут покрыты полосами из синтетического материала пружинкин. На складе имеются N полос пружинкина, длины которых равны 1, 2, …, N метров соответственно (i-я полоса имеет длину i метров).

Было решено использовать все полосы со склада, что определило длину дорожек манежа. Полосы пружинкина должны быть уложены без перекрытий и промежутков. Разрезать полосы на части нельзя. Полосы укладываются вдоль дорожек, ширина полосы пружинкина совпадает с шириной беговой дорожки.

Требуется написать программу, которая определяет, можно ли покрыть всем имеющимся материалом M дорожек, и если это возможно, то распределяет полосы пружинкина по дорожкам.