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

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

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

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

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

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

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

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

2.  В записи числа 14 чётных и нечётных цифр поровну. Число 14 чётное, дописываем к двоичной записи 0, получаем 111002  =  2810.

3.  В записи числа 28 чётных цифр больше нечётных, дописываем к двоичной записи 1, получаем 1110012  =  5710.

4.  В записи числа 57 нечётных цифр больше, дописываем к двоичной записи 0, получаем 11100102  =  11410.

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

Определите количество принадлежащих отрезку [876 544; 1 234 567 899] чисел, которые могут получиться в результате работы этого алгоритма.