На вход алгоритма подаётся натуральное число N. Алгоритм...

Задание:

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

1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:

a. если число N делится на 3, то к этой записи дописываются три последние двоичные цифры;

b. если число N на 3 не делится, то остаток от деления умножается на 3, переводится в двоичную запись и дописывается в конец числа. Полученная таким образом запись является двоичной записью искомого числа R.

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

Например, для исходного числа 12 = 1100₂ результатом является число 1100100₂ = 100, а для исходного числа 4 = 100₂ это число 10011₂ = 19.

Укажите минимальное число R, большее 151, которое может быть получено с помощью описанного алгоритма. В ответе запишите это число в десятичной системе счисления.

Решение (аналитическое):

Пункт 2 имеет три возможных исхода:

1) Число делится на 3 – к числу дописывает три последние разряда
2) Число при делении на 3 дает остаток 1 – к числу дописывается двоичная запись 3 = 11₂ (два разряда)
3) Число при делении на 3 дает остаток 2 – к числу дописывается двоичная запись 6 = 110₂ (три разряда)

Минимальное число, удовлетворяющее в качестве результата, 152:

152₁₀ = 10011000₂

Если убрать три правых разряда, получим 10011₂ = 19₁₀. То есть мы можем дописать три разряда к 19 и больше и получить значение, превосходящее 151. Однако, 19 при делении на 3 имеет остаток 1. Следовательно, нам нужно взять как минимум 20. 20 при делении на 3 имеет остаток 2. Значит, к двоичной записи будет дописано 110.

20₁₀ = 10100₂ -> 10100110₂ = 166₁₀

Если убрать два правых разряда, то получим число 100110₂ = 38₁₀. Остаток при делении на 3 равен 2. Значит, минимальное число, с остатком 1, будет 40.

40₁₀ = 101000₂ -> 10100011₂ = 163₁₀

Ответ: 163

Решение (программное):

Переберем все числа до 151 и для запишем все полученные результаты в множество. После чего найдем минимальный элемент этого множества.

res = set()
for x in range(1, 152):
    bx = bin(x)[2:]

    if x % 3 == 0:
        bx += bx[-3: ]
    else:
        bx += bin((x%3) * 3)[2:]

    R = int(bx, 2)
    if R > 151:
        res.add(R)

print(min(res)) 

Источник: Информатика с Джобсом | ЕГЭ