Question

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

1. Строится двоичная запись числа $N$.
2. К этой записи дописываются дополнительные разряды по правилу:
   - если $N$ чётное, то к двоичной записи слева дописывается `10`;
   - если $N$ нечётное, то слева приписывается `1`, а справа два нуля.

Полученная запись (содержащая как минимум на два разряда больше, чем исходная) является двоичной записью числа $R$.

Найдите максимальное значение $R$ при условии, что $N \leq 12$. Ответ запишите в десятичной системе счисления.

Accepted Answer

108

Answer

Идея решения: переберём все натуральные числа от 1 до 12, для каждого применим правило преобразования двоичной записи и найдём максимальное полученное число.

Для каждого $N$ выполняем следующие шаги:

1. Получаем двоичное представление $N$ (без префикса `0b`).
2. Применяем правило в зависимости от чётности:
   - если $N$ чётное: приписываем `10` слева;
   - если $N$ нечётное: приписываем `1` слева и `00` справа.
3. Преобразуем полученную двоичную строку в десятичное число.
4. Отслеживаем максимум.

Проверим несколько примеров:
- $N = 12$ (чётное): двоичная запись `1100`, после преобразования `101100` = $44_{10}$.
- $N = 11$ (нечётное): двоичная запись `1011`, после преобразования `110110` = $54_{10}$.
- $N = 10$ (чётное): двоичная запись `1010`, после преобразования `101010` = $42_{10}$.
- $N = 9$ (нечётное): двоичная запись `1001`, после преобразования `110010` = $50_{10}$.
- $N = 8$ (чётное): двоичная запись `1000`, после преобразования `101000` = $40_{10}$.
- $N = 7$ (нечётное): двоичная запись `111`, после преобразования `111100` = $60_{10}$.
- $N = 6$ (чётное): двоичная запись `110`, после преобразования `10110` = $22_{10}$.
- $N = 5$ (нечётное): двоичная запись `101`, после преобразования `110100` = $52_{10}$.
- $N = 4$ (чётное): двоичная запись `100`, после преобразования `10100` = $20_{10}$.
- $N = 3$ (нечётное): двоичная запись `11`, после преобразования `11100` = $28_{10}$.
- $N = 2$ (чётное): двоичная запись `10`, после преобразования `1010` = $10_{10}$.
- $N = 1$ (нечётное): двоичная запись `1`, после преобразования `1100` = $12_{10}$.

```python
maxi = 0
for n in range(1, 13):
    s = bin(n)[2:]
    if n % 2 == 0:
        s = "10" + s
    else:
        s = "1" + s + "00"
    r = int(s, 2)
    maxi = max(maxi, r)
print(maxi)
```

Максимальное значение получается при $N = 11$: двоичная запись `1011` преобразуется в `110110`, что равно $108_{10}$.

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