Задание №86290 ЕГЭ Информатике

Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом.

1.  Строится двоичная запись числа N.

2.  Если сумма цифр десятичной записи заданного числа нечётна, то в конец двоичной записи дописывается 1, если чётна  — 0.

3−4.  Пункт 2 повторяется для вновь полученных чисел ещё два раза.

5.  Результатом работы алгоритма становится десятичная запись полученного числа R.

Пример. Дано число N  =  17. Алгоритм работает следующим образом:

1.  Строим двоичную запись: 1710  =  100012.

2.  Сумма цифр числа 17 чётная, дописываем к двоичной записи 0, получаем 1000102  =  3410.

3.  Сумма цифр числа 34 нечётная, дописываем к двоичной записи 1, получаем 10001012  =  6910.

4.  Сумма цифр числа 69 нечётная, дописываем к двоичной записи 1, получаем 100010112  =  13910.

5.  Результат работы алгоритма R  =  139.

Определите количество принадлежащих отрезку [123 456 789; 1 987 654 321] чисел, которые могут получиться в результате работы этого алгоритма.