Question

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

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

Полученная запись — двоичная запись числа $R$.

**Примеры:** $6_{10} = 110_2$ → $1000_2 = 8_{10}$; $4_{10} = 100_2$ → $1101_2 = 13_{10}$.

Найдите максимальное число $N$, для которого $R < 35$.

Accepted Answer

24

Answer

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

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

```python
maxi = 0
for n in range(1, 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 < 35:
        maxi = max(maxi, n)
print(maxi)
```

Проверим на примерах:
- $N = 6 = 110_2$: сумма цифр 2 (чётная) → $10 + 0 + 0 = 1000_2 = 8$ ✓
- $N = 4 = 100_2$: сумма цифр 1 (нечётная) → $11 + 0 + 1 = 1101_2 = 13$ ✓

Программа перебирает значения до 1000 и находит, что при $N = 24$ получается $R = 34 < 35$, а при $N = 25$ получается $R \geq 35$.

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