Карточки
Тесты
Главная
Курсы
Подписка
5. Построение алгоритмов для исполнителей: #291344
На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом.
- Строится троичная запись числа $N$.
- Далее эта запись обрабатывается по следующему правилу:
- если число $N$ делится на $3$, то к этой записи дописываются две последние троичные цифры;
- если число $N$ на $3$ не делится, то остаток от деления умножается на $5$, переводится в троичную запись и дописывается в конец числа.
- Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа $11=102_3$ результатом является число $102101_3=307$, а для исходного числа $6=20_3$ это число $2020_3=60$.
Укажите минимальное число $N$, после обработки которого с помощью этого алгоритма получается число $R$, не меньшее $86$.
Рассмотрим три возможных остатка от деления $N$ на $3$.
Если $N$ делится на $3$, к записи добавляются две троичные цифры: $R=9N+(N\bmod 9)$.
При $N=9$: $R=9\cdot9+0=81<86$.
Следующее число, делящееся на $3$, — $12$, поэтому минимальный кандидат в этом случае равен $12$.
Если остаток от деления $N$ на $3$ равен $1$, дописывается троичная запись числа $5$, то есть $12_3$: $R=9N+5$.
Из условия $9N+5\geq86$ получаем $N\geq9$. Минимальное число с остатком $1$ при делении на $3$ — $10$.
Если остаток от деления $N$ на $3$ равен $2$, дописывается троичная запись числа $10$, то есть $101_3$: $R=27N+10$.
При $N=2$: $R=27\cdot2+10=64<86$.
Следующее число с остатком $2$ при делении на $3$ — $5$: $5=12_3$; $R=12101_3=145$.
Наименьшее из найденных значений $N$ равно $5$.
20
