Статья Автор: Деникина Н.В., Деникин А.В.

Приписывание слева и выбор ответа

Задача

Источник: Демо-2025

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

1. Строится двоичная запись числа N.

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

а) если число чётное, то к двоичной записи числа слева дописывается 10;

б) если число нечётное, то к двоичной записи числа слева дописывается 1 и справа дописывается 01.

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

Например, для исходного числа 4 = 100₂ результатом является число 20 = 10100₂, а для исходного числа 5 = 101₂ это число 53 = 110101₂. Укажите максимальное число R, которое может быть результатом работы данного алгоритма, при условии, что N не больше 12. В ответе запишите это число в десятичной системе счисления.


Решение

Для нечётного N результат устроен так: 1 │ запись N │ 01. Убираем добавленные разряды с обеих сторон и проверяем N.


Выполни преобразование для N = 7. Найди R.


Решение с конца: сначала выбираем выгодную ветку
Ищем максимальное значение R при условии N ≤ 12. Сначала сравним две ветки алгоритма по длине результата, а затем выберем максимально возможное N в выгодной ветке.
Проверяем основные кандидаты:
Решаем с конца Сравниваем две ветки алгоритма
Шаг 1 из 5
 

 

Решение текстом

По условию N ≤ 12, поэтому двоичная запись N содержит не более четырёх разрядов.

Для чётного N алгоритм дописывает слева 10. Поэтому результат имеет не более шести двоичных разрядов.

Для нечётного N слева дописывается 1, а справа — 01. Такая запись может содержать семь разрядов. Значит, для максимального R выгоднее искать ответ именно в нечётной ветке.

Результат в этой ветке имеет вид:

1 | N | 01

Чтобы получить максимальный результат, нужно взять максимально возможное N. Сначала проверяем N = 12:

12 = 1100₂.

Формально запись 1 | 1100 | 01 дала бы 113, но число 12 чётное. Поэтому нечётную ветку к нему применять нельзя. На самом деле для N = 12 используется чётная ветка:

10 | 1100 = 101100₂ = 44.

Следующее число — 11. Оно нечётное, поэтому для него нужная ветка разрешена:

11 = 1011₂

1 | 1011 | 01 = 1101101₂ = 109.

Число 12 больше, но не подходит нечётной ветке. Все числа меньше 11 дадут меньшую середину и, следовательно, меньший результат.

Ответ: 109.


Как ускорить — необязательно

У нечётного N результат имеет вид 1 | N | 01. При N ≤ 12 самый большой нечётный кандидат — 11, значит сразу получаем 1|1011|01₂ = 109. Чётная ветка короче и меньшего разряда.


Программное решение

Компьютеру проще проверить все разрешённые N от 1 до 12. Это независимая проверка нашего решения с конца.



Вывод программы
109

Совпало с разбором.


По правилу преобразования, без ограничения N ≤ 12, получено R = 117. Найди N.


Не потеряй балл

  • Не выбирай максимальное N вместо максимального R.

  • Не забудь условие ветки при восстановлении входа.
Печать