Карточки
Тесты
Главная
Курсы
Подписка
5. Построение алгоритмов для исполнителей: #291354
На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом.
- Строится троичная запись числа $N$.
- Далее эта запись обрабатывается по следующему правилу:
- если число $N$ делится на $3$, то к этой записи дописываются две последние троичные цифры;
- если число $N$ на $3$ не делится, то остаток от деления умножается на $5$, переводится в троичную запись и дописывается в конец числа.
- Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа $11=102_3$ результатом является число $102101_3=307$, а для исходного числа $12=110_3$ это число $11010_3=111$.
Укажите максимальное число $N$, после обработки которого с помощью этого алгоритма получается число $R$, меньшее $159$.
Рассмотрим три возможных остатка от деления $N$ на $3$.
Если $N$ делится на $3$, к записи дописываются две последние троичные цифры: $R=9N+(N\bmod 9)$.
Для $N=15$:
$15=120_3$;
$120_3\rightarrow12020_3$;
$12020_3=141<159$.
Для следующего подходящего числа $N=18$: $R=9\cdot18+0=162>159$.
Максимальный кандидат в этом случае — $15$.
Если остаток от деления $N$ на $3$ равен $1$, дописывается число $5=12_3$: $R=9N+5$.
Из условия $9N+5<159$ получаем $N<\frac{154}{9}$. Наибольшее число с остатком $1$ при делении на $3$ — $16$: $R=9\cdot16+5=149<159$.
Если остаток от деления $N$ на $3$ равен $2$, дописывается число $10=101_3$: $R=27N+10$.
Из условия $27N+10<159$ получаем $N<\frac{149}{27}$. Наибольшее число с остатком $2$ при делении на $3$ — $5$:
$R=27\cdot5+10=145<159$.
Максимальное из найденных значений: $\max(15,16,5)=16$.
20
