5 номер. Преобразование записей чисел
Преобразование двоичной записи
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи справа дописываются разряды по следующему правилу. Если число кратно 3, то дописывается 010, иначе в конец дописывается двоичная последовательность, являющаяся результатом умножения 5 на остаток от деления числа N на 3.
Например, для числа 13 двоичная запись 1101 преобразуется в запись 1101101, для числа 9 двоичная запись 1001 преобразуется в 1001010.
Полученная таким образом запись является двоичной записью искомого числа R.
Укажите значение N, в результате обработки которого будет получено минимально возможное четное значение R, большее 300. Если таких значений несколько, приведите минимальное подходящее значение.
Подсказка
Сначала выполните все шаги для одного N, сохраняя строку после каждого изменения. Затем уточните, что требуется выбрать: N, R или количество значений.
Решение
Искомая величина: Укажите значение N, в результате обработки которого будет получено минимально возможное четное значение R, большее 300. Если таких значений несколько, приведите минимальное подходящее значение.
Разделите решение на два действия: для одного входного числа точно воспроизведите алгоритм, затем отберите результаты по условию задачи. Храните запись числа строкой; основание используемой системы счисления — 2.
Дописывание справа реализуется как s + suffix, слева — как prefix + s. Добавляйте ровно указанную последовательность символов, включая нули. Числовое сложение вместо соединения строк здесь меняет алгоритм.
После завершения всех преобразований получите числовой результат: R = int(s, 2). Ограничения на величину R проверяйте численно: лексикографический порядок строк не совпадает с порядком чисел.
Нужно минимизировать выходное R. Собирайте подходящие выходные значения и выбирайте минимум: первое подходящее N не обязательно даёт наименьший R, поскольку разные ветви алгоритма могут менять порядок результатов.
Строгое «больше» означает >, а «не меньше» — >=; аналогично различайте верхние границы. Диапазон перебора определяйте из ограничений и изменения длины записи, а не произвольной константой. Пример из условия помогает проверить отдельный проход алгоритма.
Ответ: 39.