Задание №5. Короткий конспект
Вход и результат, дописывание и замена цифр, чётность и границы перебора: основные опоры для решения задания №5.
N — входное число, R — результат преобразования. Алгоритм меняет запись числа; ответом может быть вход, результат или вход, соответствующий выбранному результату.
Порядок решения
- Из вопроса выделяются условие отбора и искомая величина: например, R>100, найти минимум N.
- Для одного входа записывается вся цепочка изменений. Каждый следующий шаг использует именно ту запись, которую указывает условие.
- Готовая запись переводится в число в нужном основании и проверяется ограничение.
- Сравниваются нужные величины; обосновывается, почему остальные входы не могут улучшить ответ.
Изменение записи
При дописывании справа k цифр в основании b:
R=N\cdot b^k+D,
где D — значение добавленного фрагмента. Длина считается вместе с нулями: добавление 01 в двоичной системе означает R=4N+1.
При добавлении слева используется длина исходной записи. При замене старые цифры убираются: для двух левых разрядов '10' + s[2:], а не '10' + s.
Запись в Python
| Действие | Запись |
|---|---|
| Двоичные цифры числа | s = bin(n)[2:] |
| Значение двоичной / троичной строки | int(s, 2) / int(s, 3) |
| Чётность числа | n % 2 |
| Чётность суммы двоичных цифр | s.count('1') % 2 |
| Последние три символа | s[-3:] |
Служебное начало 0b не является частью двоичной записи. В троичной системе допустимы цифры 0, 1, 2; промежуточное число перед дописыванием переводится именно в это основание.
Два последовательных бита чётности
Если каждый бит — остаток от деления суммы цифр текущей записи на 2, второй бит всегда 0. Добавляется либо 00, либо 10, поэтому R=4N или R=4N+2.
В EGE-05-0047 ↗: 25\to11001_2\to110011_2\to1100110_2=102. При N\leq24 результат не больше 98. Для условия R>100 минимум входа равен 25.
Возможные ловушки
- Минимум входа и минимум результата различаются. Для минимального N подходит первый удачный вход по возрастанию. Для минимального R нужно сравнение результатов: в EGE-05-0020 ↗ 20\to166, но 40\to163.
- Повторный шаг использует новую запись. В EGE-05-0047 ↗ повторный подсчёт по старой строке даёт неверный второй бит.
- Ноль в суффиксе занимает разряд. В EGE-05-0011 ↗ добавление 01 нельзя заменить добавлением 1: исходные цифры сдвинутся на разное число позиций.
- Граница и ответ проверяются отдельно. «Больше» означает >, «не меньше» — \geq. В EGE-05-0002 ↗ отбираются результаты R\geq200, но требуется минимальный вход.
Если доказано R>N и уже найден подходящий результат R_0, то для меньшего результата достаточно входов N<R_0. Для другого алгоритма граница обосновывается заново.
Для максимума при R\leq T и доказанном R>N проверяются входы N<T. Среди подходящих пар выбирается наибольшее N или R согласно вопросу. Пример поиска максимума результата: EGE-05-0003 ↗.