Карточки
Тесты
Главная
Курсы
Куратор
Подписка
5. Построение алгоритмов для исполнителей: #291356
На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом.
- Строится троичная запись числа $N$.
- Далее эта запись обрабатывается по следующему правилу:
- если число $N$ делится на $3$, то к этой записи дописываются две последние троичные цифры;
- если число $N$ на $3$ не делится, то остаток от деления умножается на $5$, переводится в троичную запись и дописывается в конец числа.
- Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа $11_{10}=102_3$ результатом является число $102101_3=307_{10}$, а для исходного числа $12_{10}=110_3$ это число $11010_3=111_{10}$.
Укажите минимальное число $R$, большее $180$, которое может быть получено с помощью описанного алгоритма. В ответе запишите это число в десятичной системе счисления.
Рассмотрим три возможных остатка от деления $N$ на $3$.
Если $N$ делится на $3$, к записи дописываются две последние троичные цифры: $R=9N+(N\bmod 9)$.
Для $N=18$:
$18_{10}=200_3$;
$200_3\rightarrow20000_3$;
$20000_3=162_{10}<180$.
Для следующего кратного $3$ числа $N=21$:
$21_{10}=210_3$;
$210_3\rightarrow21010_3$;
$21010_3=192_{10}$.
Если остаток от деления $N$ на $3$ равен $1$, дописывается число $5=12_3$: $R=9N+5$.
При $N=19$: $R=9\cdot19+5=176<180$.
Следующее число с остатком $1$ при делении на $3$ — $22$: $R=9\cdot22+5=203$.
Если остаток от деления $N$ на $3$ равен $2$, дописывается число $10=101_3$: $R=27N+10$.
При $N=5$: $R=27\cdot5+10=145<180$.
Следующее число с остатком $2$ при делении на $3$ — $8$: $R=27\cdot8+10=226$.
Минимальное из полученных значений: $\min(192,203,226)=192$.
20
