Question

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

1. Строится двоичная запись числа $N$.
2. Эта запись обрабатывается по правилу:
   - если сумма цифр в двоичной записи чётная, то справа дописывается 0, а два левых разряда заменяются на 10;
   - если сумма цифр в двоичной записи нечётная, то справа дописывается 1, а два левых разряда заменяются на 11.
3. Полученная запись переводится в десятичную систему и выводится.

Например: $6_{10} = 110_2$ → сумма цифр 2 (чётная) → $110_2$ становится $1000_2 = 8_{10}$; $4_{10} = 100_2$ → сумма цифр 1 (нечётная) → $100_2$ становится $1101_2 = 13_{10}$.

Найдите максимальное число $N$, после обработки которого получается число $R$, не превышающее 19.

Accepted Answer

12

Answer

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

Алгоритм:
1. Для каждого числа $n$ получаем его двоичное представление.
2. Подсчитываем количество единиц в этом представлении.
3. Если количество единиц чётное, дописываем 0 справа и заменяем первые два бита на 10; если нечётное — дописываем 1 справа и заменяем первые два бита на 11.
4. Переводим полученную двоичную строку в десятичное число.
5. Если результат не превышает 19, сохраняем исходное число $n$.
6. Выводим максимальное из найденных чисел.

```python
result = []
for n in range(1000):
    s = bin(n)[2:]
    if s.count('1') % 2 == 0:
        s = '10' + s[2:] + '0'
    else:
        s = '11' + s[2:] + '1'
    r = int(s, 2)
    if r <= 19:
        result.append(n)

print(max(result))
```

Проверим несколько значений:
- $n = 6$: $110_2$, сумма 2 (чётная) → $10\,10_2 = 1000_2 = 8$ ✓
- $n = 4$: $100_2$, сумма 1 (нечётная) → $11\,00_2 + 1 = 1101_2 = 13$ ✓
- $n = 12$: $1100_2$, сумма 2 (чётная) → $10\,00_2 + 0 = 1000_2 = 8$ ✓
- $n = 13$: $1101_2$, сумма 3 (нечётная) → $11\,01_2 + 1 = 1101_2 + 1 = 11011_2 = 27 > 19$ ✗

Максимальное число, дающее результат ≤ 19, равно 12.

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