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