5 номер. Преобразование записей чисел
Преобразование троичной записи
(М. Шагитов) Алгоритм принимает на вход натуральное число N и строит на его основе новое число R следующим образом:
1. Строится троичная запись числа N.
2. Затем данная запись обрабатывается по следующим критериям:
а) Если число N делится на 5, к троичной записи числа N добавляются его последние три цифры в троичной записи.
б) Если число N не делится на 5, то остаток от деления N на 5 умножается на 5, переводится в троичную запись и присоединяется к концу троичной записи числа N.
3. Полученная запись представляет собой троичное представление искомого числа R.
Результат переводится в десятичную систему и отображается на экране.
В качестве примера, если исходное число равно 10 (то есть 101₃ в троичной системе), то результат будет равен 101101₃ (это 280 в десятичной системе). Если исходное число равно 4 (или 11₃ в троичной системе), то результат будет равен 11202₃ (то есть 128 в десятичной системе).
Необходимо определить максимальное число N, для которого, после обработки в рамках описанного алгоритма, получается число R, меньшее 5496.
Подсказка
Сначала выполните все шаги для одного N, сохраняя строку после каждого изменения. Затем уточните, что требуется выбрать: N, R или количество значений.
Решение
Разделите решение на два действия: для одного входного числа точно воспроизведите алгоритм, затем отберите результаты по условию задачи. Храните запись числа строкой; основание используемой системы счисления — 3.
Если дописывается остаток от деления, отдельно вычислите остаток и запишите его в требуемой системе счисления. Десятичная строка остатка и его троичная запись могут различаться.
После завершения всех преобразований получите числовой результат: R = int(s, 3). Ограничения на величину R проверяйте численно: лексикографический порядок строк не совпадает с порядком чисел.
Отбирайте ту величину, о которой спрашивается в последнем предложении: исходное число и результат алгоритма нельзя подменять друг другом. Для наименьшего входа рассматривайте допустимые N по возрастанию; для наибольшего проверяйте весь обоснованный диапазон.
Строгое «больше» означает >, а «не меньше» — >=; аналогично различайте верхние границы. Диапазон перебора определяйте из ограничений и изменения длины записи, а не произвольной константой. Пример из условия помогает проверить отдельный проход алгоритма.
Ответ: 606.