Задание 5 ЕГЭ, информатика: Посимвольное двоичное преобразование

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

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

2.  В конец двоичной записи добавляется двоичный код остатка от деления числа N на 4.

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

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

1.  Строим двоичную запись: 13₁₀  =  1101₂.

2.  Остаток от деления 13 на 4 равен 1, добавляем к двоичной записи цифру 1, получаем 11011₂  =  27₁₀.

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

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

1.  Строим двоичную запись: 14₁₀  =  1110₂.

2.  Остаток от деления 14 на 4 равен 2, добавляем к двоичной записи цифры 10 (10₂  =  2₁₀), получаем 111010₂  =  58₁₀.

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

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