Question

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

1. Строится двоичная запись числа $N$.
2. Далее эта запись обрабатывается по следующему правилу:
   - если число $N$ делится на 3, то к этой записи дописываются три последние двоичные цифры;
   - если число $N$ на 3 не делится, то остаток от деления умножается на 3, переводится в двоичную запись и дописывается в конец числа.

Полученная таким образом запись является двоичной записью искомого числа $R$.

Например:
- для $N = 12_{10} = 1100_2$ результатом является $11001001_2 = 201_{10}$;
- для $N = 4_{10} = 100_2$ результатом является $10011_2 = 19_{10}$.

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

Accepted Answer

163

Answer

Идея решения: перебрать все натуральные числа $N$ в разумном диапазоне, применить к каждому описанный алгоритм преобразования, собрать все полученные значения $R > 151$ и найти среди них минимальное.

Алгоритм работает следующим образом:

1. Для каждого числа $N$ получаем его двоичное представление.
2. Проверяем делимость $N$ на 3:
   - если $N \equiv 0 \pmod{3}$, дописываем три последние цифры двоичной записи;
   - если $N 
ot\equiv 0 \pmod{3}$, вычисляем $(N \bmod 3) 	imes 3$, переводим в двоичную форму и дописываем.
3. Полученную двоичную строку преобразуем в десятичное число $R$.
4. Если $R > 151$, добавляем его в список.
5. Возвращаем минимум из собранных значений.

```python
results = []
for n in range(1, 10000):
    s = bin(n)[2:]
    if n % 3 == 0:
        s += s[-3:]
    else:
        remainder = (n % 3) * 3
        s += bin(remainder)[2:]
    r = int(s, 2)
    if r > 151:
        results.append(r)

print(min(results))
```

Программа перебирает числа от 1 до 9999, применяет преобразование и собирает все результаты, превышающие 151. Минимальное значение из полученного набора — искомый ответ.

Задание №5Системы счисления и арифметикаЕГЭ по информатике