ЕГЭ по информатике 2020, вариант Москва
Системы счисления
Часть 1, № 6
Задание взято с сайта
http://kotolis.ru/realegeinf_2020

Условие. На вход алгоритма подаётся натуральное число N.
Алгоритм по нему строит новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописываются разряды по следующему правилу:
а) если число чётное, то к двоичной записи числа в конце дописывается 1 и 0;
б) если число нечётное, то к двоичной записи числа в конце дописывается 01.
Полученная таким образом запись является двоичной записью искомого числа R. Укажите наибольшее число R меньшее 109, которое может получиться после обработки этого алгоритма (в результате работы этого алгоритма). В ответе это число запишите в десятичной системе.

Решение.
Вначале посмотрим, что происходит с числом после приписывания к нему двух цифр в десятичной системе счисления.
Пусть число N записано в десятичной системе счисления. Если мы к концу этого числа припишем две цифры xy, то умножим исходное число на 100 (10^2) и прибавим к нему число xy:
R = N * 10^2 + x * 10^1 + y * 1.

Приписывание двух цифр 01(10) в двоичной системе счисления аналогично умножению исходного числа на 4 (2^2) в десятичной с последующим прибавлением числа 1(2):
а) N – нечётное
R = N * 2^2 + 0 * 2^1 + 1 * 1 = 4N + 1.
Теперь найдём наибольшее нечётное R < 109:
R < 109; 4N < 108; N < 27; N = 25.
R = 4*25 + 1 = 101.

б) N – чётное
R = N * 2^2 + 1 * 2^1 + 0 * 1 = 4N + 2.
R < 109; 4*N < 107; N < 26,75; N = 26.
R = 4*26 + 2 = 106.

Ответ: 106 .