5 номер. Преобразование записей чисел
Преобразование троичной записи
На вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R следующим образом:
1. Строится троичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 3, то к этой записи справа дописываются цифры 21, а слева – цифра 1;
б) если число N на 3 не делится, то остаток от деления числа N на 3 умножается на 5, переводится в троичную систему счисления и дописывается в конец числа.
Полученная таким образом запись является троичной записью искомого числа R. Например, для исходного числа 11 = 102₃ результатом является число 102101₃ = 307, а для исходного числа 12 = 110₃ результатом является число 111021₃ = 358. Укажите максимальное нечётное число N, после обработки которого с помощью этого алгоритма получается число R, не превышающее 1130.
Подсказка
Сначала выполните все шаги для одного N, сохраняя строку после каждого изменения. Затем уточните, что требуется выбрать: N, R или количество значений.
Решение
Искомая величина: Полученная таким образом запись является троичной записью искомого числа R. Например, для исходного числа 11 = 102₃ результатом является число 102101₃ = 307, а для исходного числа 12 = 110₃ результатом является число 111021₃ = 358. Укажите максимальное нечётное число N, после обработки которого с помощью этого алгоритма получается число R, не превышающее 1130.
Разделите решение на два действия: для одного входного числа точно воспроизведите алгоритм, затем отберите результаты по условию задачи. Храните запись числа строкой; основание используемой системы счисления — 3.
Дописывание справа реализуется как s + suffix, слева — как prefix + s. Добавляйте ровно указанную последовательность символов, включая нули. Числовое сложение вместо соединения строк здесь меняет алгоритм.
Если дописывается остаток от деления, отдельно вычислите остаток и запишите его в требуемой системе счисления. Десятичная строка остатка и его троичная запись могут различаться.
После завершения всех преобразований получите числовой результат: R = int(s, 3). Ограничения на величину R проверяйте численно: лексикографический порядок строк не совпадает с порядком чисел.
Отбирайте ту величину, о которой спрашивается в последнем предложении: исходное число и результат алгоритма нельзя подменять друг другом. Для наименьшего входа рассматривайте допустимые N по возрастанию; для наибольшего проверяйте весь обоснованный диапазон.
Строгое «больше» означает >, а «не меньше» — >=; аналогично различайте верхние границы. Диапазон перебора определяйте из ограничений и изменения длины записи, а не произвольной константой. Пример из условия помогает проверить отдельный проход алгоритма.
Ответ: 121.