Карточки
Тесты
Главная
Курсы
Куратор
Подписка
5. Построение алгоритмов для исполнителей: #291348
На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число $R$ следующим образом.
- Строится двоичная запись числа $N$.
- Далее эта запись обрабатывается по следующему правилу:
- если число $N$ делится на $3$, то к этой записи дописываются три последние двоичные цифры;
- если число $N$ на $3$ не делится, то остаток от деления умножается на $3$, переводится в двоичную запись и дописывается в конец числа.
- Результат переводится в десятичную систему и выводится на экран.
Например, для исходного числа $12_{10}=1100_2$ результатом является число $1100100_2=100_{10}$, а для исходного числа $4_{10}=100_2$ это число $10011_2=19_{10}$.
Укажите максимальное число $R$, не превышающее $208$, которое может быть получено с помощью описанного алгоритма. В ответе запишите это число в десятичной системе счисления.
Рассмотрим три возможных остатка от деления $N$ на $3$.
Если $N$ делится на $3$, дописываются три последние цифры двоичной записи: $R=8N+(N\bmod 8)$.
Наибольшее подходящее число $N$, кратное $3$, — $24$: $R=8\cdot24+0=192$.
При следующем числе $N=27$: $R=8\cdot27+3=219>208$.
Если остаток от деления $N$ на $3$ равен $1$, дописывается число $3=11_2$: $R=4N+3$.
Из условия $4N+3\leq208$ получаем $N\leq51$. Наибольшее число, не превосходящее $51$ и дающее остаток $1$ при делении на $3$, — $49$: $R=4\cdot49+3=199$.
Если остаток от деления $N$ на $3$ равен $2$, дописывается число $6=110_2$: $R=8N+6$.
Из условия $8N+6\leq208$ получаем $N\leq25$. Наибольшее число, не превосходящее $25$ и дающее остаток $2$ при делении на $3$, — $23$: $R=8\cdot23+6=190$.
Максимальное из полученных значений: $\max(192,199,190)=199$.
20
