Задание №5. Преобразование записи числа

Алгоритм получает число N, меняет его запись и выдаёт число R. Например, к двоичной записи добавляются цифры или часть разрядов заменяется. Одно выполнение алгоритма даёт одну пару «вход — результат». Чтобы найти минимум или максимум, нужно ещё определить, какие пары подходят под условие и что именно среди них сравнивается.

Вход, запись и результат

Число и его запись — разные вещи. 25_{10}=11001_2: значение одно, а цифры зависят от системы счисления. Нижний индекс показывает основание. Алгоритм работает с цифрами записи, а условие на результат обычно задаётся для числа в десятичной системе.

Третья формулировка встречается, например, в задании EGE-05-0028 ↗. Она не равнозначна просьбе найти наименьшее входное число.

Пример: два последовательных бита чётности

В задании EGE-05-0047 ↗ к двоичной записи дважды дописывается справа остаток от деления суммы её цифр на 2. Во второй раз используется уже изменённая запись. Требуется найти наименьшее N, для которого R>100.

1. Что происходит с одной записью

Сумма двоичных цифр равна количеству единиц: нули ничего не добавляют. Остаток от деления этой суммы на 2 равен 0 для чётной суммы и 1 для нечётной. Этот добавляемый разряд называют битом чётности.

Для проверки работы алгоритма подходит N=25. Его запись меняется так:

Получена запись 1100110_2. Её значение:

R=64+32+4+2=102.

Число 25 подходит: результат больше 100. Пока это проверка одного входа; минимальность ещё требует обоснования.

2. Почему меньшие входные числа не подходят

После первого шага число единиц всегда чётное. Поэтому второй добавляемый бит всегда равен 0. В зависимости от исходной чётности справа добавляется либо 00, либо 10.

Два новых двоичных разряда сдвигают исходную запись на две позиции: это умножение числа на 2^2=4. Суффикс 00_2 добавляет 0, а 10_2 — 2. Значит:

R=4N\quad\text{или}\quad R=4N+2.

Для любого N\leq24 даже больший из двух результатов не превышает 4\cdot24+2=98. Все меньшие входы исключены, а N=25 даёт 102. Ответ — 25, поскольку спрашивается входное число.

3. Та же последовательность в Python

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

for n in range(1, 26):
    s = bin(n)[2:]
    s += str(s.count('1') % 2)
    s += str(s.count('1') % 2)
    r = int(s, 2)
    if r > 100:
        print(n)
        break

bin(n)[2:] оставляет двоичные цифры без служебного начала 0b. Вторая строка дописывания считает единицы заново, уже после первой. int(s, 2) читает запись в основании 2. break завершает поиск на первом подходящем входе; здесь это правильно, потому что входы проверяются по возрастанию и нужен минимум N.

Когда первый подходящий вход не даёт нужного ответа

В задании EGE-05-0020 ↗ правило другое. Если N делится на 3, справа копируются три последние двоичные цифры. Иначе остаток от деления умножается на 3, переводится в двоичную запись и дописывается справа. Нужно найти минимальное R>151.

Первый подходящий вход при переборе по возрастанию — 20, но более поздний вход 40 даёт меньший результат. Таблица показывает причину, по которой ранняя остановка неверна; для окончательного ответа сравниваются все допустимые результаты.

Результат 166 уже найден. По этому правилу исходная запись сохраняется и справа добавляется хотя бы одна цифра, поэтому R>N. При N\geq166 улучшить найденный результат невозможно. Достаточно проверить входы от 1 до 165:

results = []
for n in range(1, 166):
    s = bin(n)[2:]
    if n % 3 == 0:
        s += s[-3:]
    else:
        s += bin((n % 3) * 3)[2:]
    r = int(s, 2)
    if r > 151:
        results.append(r)
print(min(results))

Перебор даёт 163. Это ответ на вопрос о результате, а соответствующий вход равен 40. Срез s[-3:] копирует цифры, а не десятичное число.

Когда нужен максимум

В EGE-05-0003 ↗ применяется то же правило, но требуется наибольшее R\leq208. Так как здесь R>N, подходят только входы N<208. После проверки этого конечного диапазона среди допустимых результатов выбирается наибольший: 199, полученный при N=49. Если бы требовался максимум входа, сравнивались бы значения N подходящих пар. При замене или удалении разрядов граница поиска обосновывается отдельно: сохранение неравенства R>N не следует из одного названия операции.

Другие изменения записи

Общий порядок сохраняется: условие ветвления → изменение записи → перевод результата → проверка вопроса. При этом сами изменения могут различаться.

• Цифры слева и справа. В EGE-05-0011 ↗ чётный вход получает слева 10, нечётный — слева 1 и справа 01. Например, 5_{10}=101_2 превращается в 110101_2=53_{10}. Добавление слева зависит от длины исходной записи.
• Замена разрядов. В EGE-05-0001 ↗ сначала дописывается бит, затем заменяются два левых разряда. Для N=6 путь такой: 110\to1100\to1000, поэтому R=8. Замена не увеличивает длину записи: старые цифры заменяются новыми.
• Троичная система. В EGE-05-0004 ↗ используются цифры 0, 1, 2. Для N=11=102_3 остаток от деления на 3 равен 2. Умножение на 5 даёт 10_{10}=101_3, поэтому получается 102101_3=307_{10}. Добавляется троичная запись 101, а не десятичная запись 10.

Связь записи с арифметикой и перевод между основаниями разобраны в статье «Позиционная запись числа и её преобразования».

Возможные ловушки

Ниже несколько особенностей условий, которые могут изменить ход решения.

• Чётность числа вместо чётности суммы цифр. В EGE-05-0047 ↗ проверяется сумма двоичных цифр. Числа 4 и 6 оба чётные, но 100_2 содержит одну единицу, а 110_2 — две. Проверка n % 2 здесь не заменяет s.count('1') % 2.
• Повторение операции над старой записью. В том же задании второй бит вычисляется после первого. Если дважды использовать исходное число единиц, для N=25 ошибочно получится суффикс 11 вместо 10, а результат будет 103 вместо 102.
• Потерянный ноль в добавляемом фрагменте. В EGE-05-0011 ↗ справа дописывается именно 01. Это два новых разряда, хотя числовое значение фрагмента равно 1. Для входа 5 замена суффикса на 1 дала бы 11011_2=27 вместо 53.
• Добавление вместо замены. В EGE-05-0001 ↗ команда «два левых разряда заменяются на 10» означает '10' + s[2:] для уже изменённой строки. Запись '10' + s сохраняет старые разряды и создаёт другое число.
• Первый результат принят за наименьший. В EGE-05-0020 ↗ результаты при возрастании входов могут уменьшаться. Поэтому минимум R ищется сравнением результатов; остановка на первом подходящем N не подходит.
• Изменён знак границы. В EGE-05-0002 ↗ «не меньше 200» означает R\geq200, а в EGE-05-0004 ↗ «больше 133» означает R>133. Равенство допускается только в первом случае. Условие относится к результату; величина, которую требуется записать, определяется отдельно.