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

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

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

2. Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется та цифра, которая встречается реже.

3. Шаг 2 повторяется ещё два раза

4. Результат переводится в десятичную систему.

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

1. Двоичная запись числа N: 10011.

2. В полученной записи нулей меньше, чем единиц, в конец записи добавляется 0. Новая запись: 100110.

3. В текущей записи нулей и единиц поровну, в конец записывается последняя цифра, это 0. Получается 1001100. В этой записи единиц меньше, в конец добавляется 1: 10011001.

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

При каком наименьшем числе N >255в результате работы алгоритма получится число, кратное 3?