Задание 5: подбор исходного числа

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

Прямой путь — перебирать все числа подряд и прогонять алгоритм — работает, но медленно и ненадёжно: на экзамене нет компьютера, а границы перебора часто велики.

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

Общая схема решения.

Шаг 1. Прочитать алгоритм как правило для двоичной записи. Типичные формулировки: «если число чётное, дописать справа 0, иначе дописать 1», «подсчитать сумму цифр и дописать её остаток от деления на 2». Переведите словесное описание в одну фразу вида «к записи N дописываются такие-то биты».

Шаг 2. Записать результат формулой. Дописать бит справа — значит умножить число на 2 и прибавить этот бит. Дописать два бита — умножить на 4 и прибавить двузначное двоичное число. Это ключ: длинное словесное описание превращается в короткое арифметическое выражение вида R = 4·N + c, где c зависит от свойств N.

Шаг 3. Подставить условие на результат и решить неравенство относительно N, разобрав случаи по значению c. Случаев обычно два-три: чётное и нечётное, либо остаток от деления на 4.

Шаг 4. Проверить найденное число прогоном алгоритма. Этот шаг обязателен: он занимает минуту и ловит ошибку в разборе случаев.

Шаг 5. Убедиться, что найдено именно крайнее значение. Если ищется наименьшее N, проверьте соседнее меньшее — оно должно условию не удовлетворять. Это самая частая потеря балла: найдено подходящее число, но не наименьшее.

Условие линии 5 всегда состоит из трёх пронумерованных пунктов и одного вопроса. Вот оно целиком, дословно из банка:

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

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

2. Далее эта запись обрабатывается по правилу: если N кратно 3, в конец записи дописывается 00, иначе — 11.

3. Полученная запись переводится в десятичную систему счисления — это и есть число R.

Укажите минимальное число N, после обработки которого получается число R, не меньшее 64».

Пункт 1 задаёт систему счисления. Чаще всего двоичная, но бывает и троичная, и восьмеричная — читать надо внимательно, потому что от этого зависит вся арифметика.

Пункт 2 — само правило, и оно меняется от варианта к варианту. В банке встречаются: дописать цифры в конец, дописать в начало, вставить в середину, заменить две последние цифры, дописать по-разному в зависимости от чётности N, от кратности трём, от чётности числа единиц в записи.

Пункт 3 возвращает результат в десятичную систему.

Вопрос — это отдельная ловушка: минимальное или максимальное N, «не меньше» или «строго больше». Перепутать направление легко, и тогда верная программа даст неверный ответ.

Прежде чем писать программу, стоит заметить, что операции над записью числа — это обычная арифметика, и в такой форме задача часто решается устно.

Дописать цифру d справа в системе с основанием p — значит умножить число на p и прибавить d. В десятичной это очевидно: приписать к 47 семёрку — получить 477 = 47 · 10 + 7. В двоичной ровно так же: приписать 1 к числу N — получить 2N + 1.

Отсюда правила линии 5 переводятся в формулы:

— дописать в конец 00 — это 4N (два разряда, то есть умножение на 2², и ничего не прибавляем);

— дописать в конец 11 — это 4N + 3 (двоичное 11 это тройка);

— дописать 1 в конец — это 2N + 1, дописать 0 — это 2N;

— в троичной системе дописать цифру d справа — это 3N + d.

Дописать цифру слева так просто не выражается: приписать единицу к k-разрядной двоичной записи — значит прибавить 2^k. Здесь придётся разбирать случаи по числу разрядов.

Вставить в середину — тоже разбор случаев, и его удобнее доверить программе.

Зачем это знать, если есть компьютер? Затем, что формула сразу показывает ответ без перебора. Правило «00 при кратности трём, иначе 11» даёт R = 4N для кратных трём и R = 4N + 3 для остальных. Условие R ≥ 64 превращается в два неравенства, и решаются они в уме.

Минимальное или максимальное. Самая дорогая ошибка линии: программа верна, направление перебора нет. Подчеркните в условии слово «минимальное» или «наибольшее» прежде, чем писать цикл.

Нестрогое неравенство против строгого. «R не меньше 64» — это R ≥ 64, и число 64 подходит. «R больше 64» — это R > 64, и 64 уже не годится. Разница в один шаг перебора и в целый балл.

Система счисления в пункте 1. Если написано «троичная запись», то bin не годится: нужна своя функция перевода. Прочитать «двоичная» там, где написано «троичная», проще, чем кажется, — пункты выглядят одинаково из варианта в вариант.

Приписывание не равно сложению. В сюжетах с цифрами «приписать P1 к P2» — это склейка строк. Арифметическая формула P2 · 100 + P1 сработает не всегда.

Диапазон перебора. «Четырёхзначное число» — это 1000…9999, а не 1…9999. И наоборот, для сюжетов с двоичной записью верхнюю границу приходится прикидывать: если R растёт примерно вчетверо, для R ≈ 1000 хватит N до 300.

Проверка соседа. Найдя ответ, посчитайте R для соседнего числа в «запрещённую» сторону. Если оно тоже подходит, значит, минимум найден не тот.

Линия 5 — это алгоритм из трёх пунктов и вопрос про крайнее значение исходного числа. Решается она двумя способами, и оба полезны.

Программой. Написать функцию R(N), дословно повторяющую пункты условия, и перебрать N в разумном диапазоне. Направление цикла определяется словом «минимальное» или «наибольшее»: вверх с прерыванием на первом совпадении — для минимума, вверх без прерывания с запоминанием — для максимума.

Арифметикой. Операции над записью — это умножение и сложение: дописать d справа в системе с основанием p значит умножить на p и прибавить d. Дописать 00 в двоичной — это 4N, дописать 11 — это 4N + 3. Правило с условием («если кратно 3») даёт две формулы, каждая решается неравенством, и из двух кандидатов берётся нужный.

Второй способ не только быстрее — он показывает, что кандидатов ровно столько, сколько ветвей в правиле, и потому страхует от промаха перебора.

Полезные строчки Python для этой линии: bin(N)[2:] — двоичная запись без приставки, int(s, 2) — обратно в число, s[:k//2] + '0' + s[k//2:] — вставка в середину, s.count('1') — число единиц, [int(d) for d in str(K)] — цифры десятичного числа.