Карточки
Тесты
Главная
Курсы
Подписка
5. Построение алгоритмов для исполнителей: #291357
На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом.
- Строится троичная запись числа $N$.
- Далее эта запись обрабатывается по следующему правилу:
- если число $N$ делится на $3$, то слева к нему приписывается «$1$», а справа «$02$»;
- если число $N$ на $3$ не делится, то остаток от деления на $3$ умножается на $5$, переводится в троичную запись и дописывается в конец числа.
- Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа $11_{10}=102_3$ результатом является число $102101_3=307_{10}$, а для исходного числа $12_{10}=110_3$ это число $111002_3=353_{10}$.
Укажите минимальное число $N$, после обработки которого с помощью этого алгоритма получается число $R$, не меньшее $177$.
Рассмотрим возможные остатки от деления $N$ на $3$.
Если $N$ делится на $3$, проверим ближайшие значения:
$N=6_{10}=20_3$;
$20_3\rightarrow12002_3=137_{10}<177$.
Следующее число, делящееся на $3$:
$N=9_{10}=100_3$;
$100_3\rightarrow110002_3=326_{10}$.
Минимальный кандидат в этом случае — $9$.
Если остаток от деления $N$ на $3$ равен $1$, дописывается число $5_{10}=12_3$: $R=9N+5$.
Из условия $9N+5\geq177$ получаем $N\geq20$. Наименьшее такое число с остатком $1$ при делении на $3$ — $22$.
Если остаток от деления $N$ на $3$ равен $2$, дописывается число $10_{10}=101_3$: $R=27N+10$.
Из условия $27N+10\geq177$ получаем $N\geq7$. Наименьшее число с остатком $2$ при делении на $3$ — $8$:
$8_{10}=22_3$;
$22_3\rightarrow22101_3=226_{10}$.
Минимальное из найденных значений: $\min(9,22,8)=8$.
20
