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

Замена первых разрядов

Задача

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

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

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

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

а) если сумма цифр в двоичной записи числа чётная, то к этой записи справа дописывается 0, а затем два левых разряда заменяются на 10;

б) если сумма цифр в двоичной записи числа нечётная, то к этой записи справа дописывается 1, а затем два левых разряда заменяются на 11.

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

Например, для исходного числа 6 = 110₂ результатом является число 1000₂ = 8, а для исходного числа 4 = 100₂ результатом является число 1101₂ = 13.

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


Подставь потерянный разряд

Первый бит натурального числа — 1. Второй после замены неизвестен: поставь 0, затем 1 и проверь каждую исходную запись. Для минимального N отдельно исключи все меньшие входы.


Выполни алгоритм для N = 14. Найди R.


Решение с конца: сначала восстановим вход, затем докажем минимум
Ищем минимальное N, для которого после выполнения алгоритма получается R > 40. Сначала разберём, как обращать преобразование назад, а затем отдельно докажем минимальность входа.
Решение состоит из двух частей:
Решаем с конца Берём возможный результат R = 42
Шаг 1 из 7
 
 

 

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

Сначала посмотрим, какой вход мог дать результат R = 42 = 101010₂.

Последний разряд результата был дописан алгоритмом, поэтому убираем его. Первые два разряда результата были заменены, поэтому исходное значение второго бита потеряно.

Получаем две возможные исходные записи:

10101₂ = 21
11101₂ = 29

Для N = 21 в записи три единицы. По правилу получается 111011₂ = 59, поэтому этот вариант не подходит.

Для N = 29 в записи четыре единицы. После дописывания 0 и замены начала получается:

11101 → 111010 → 101010₂ = 42.

Значит, N = 29 действительно может дать R = 42. Но это ещё не ответ: требуется найти минимальное N, для которого R > 40.

Результат должен быть больше 40. Даже максимальное пятибитное число 11111₂ = 31 меньше 40. Следовательно, R должен иметь не менее шести бит.

Алгоритм добавляет один разряд, а последующая замена первых двух разрядов длину записи не меняет. Значит, исходное N должно иметь не менее пяти бит.

Наименьшее пятибитное натуральное число:

N = 10000₂ = 16.

В этой записи одна единица. Сначала дописываем 1:

10000 → 100001

Затем по правилу заменяем первые два разряда на 11:

100001 → 110001₂ = 49.

Получили 49 > 40, значит N = 16 подходит. Все меньшие N имеют не более четырёх бит, поэтому после добавления одного бита результат будет иметь не более пяти бит и не сможет быть больше 40.

Ответ: 16.


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

Для R = 42 нашли N = 29, но N = 16 даёт 49 и тоже проходит. Ищем минимальное N, поэтому выбираем вход, а не наименьший результат.


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

Здесь в ответе требуется N. Программа перебирает N по возрастанию и останавливается на первом входе, который даёт R > 40.



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

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


Получено R = 40. Восстанови N, проверяя чётность исходной суммы цифр.


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

  • Не считай заменённые биты исходными: они потеряны.
  • Не ищи минимальное R, когда спрашивают минимальное N.
Печать