На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 3, то к этой записи дописываются её три последние двоичные цифры;
б) если число N на 3 не делится, то остаток от деления умножается на 3, переводится в двоичную запись и дописывается в конец числа.
Полученная таким образом запись является двоичной записью искомого числа R.
Например, для N = 12 (1100₂) получается 1100100₂ = 100, а для N = 4 (100₂) — 10011₂ = 19.
Укажите минимальное натуральное число N, после обработки которого получается число R, не меньше 500.
В ответе запишите целое число.
1. Строится двоичная запись числа N.
2. Далее эта запись обрабатывается по следующему правилу:
а) если число N делится на 3, то к этой записи дописываются её три последние двоичные цифры;
б) если число N на 3 не делится, то остаток от деления умножается на 3, переводится в двоичную запись и дописывается в конец числа.
Полученная таким образом запись является двоичной записью искомого числа R.
Например, для N = 12 (1100₂) получается 1100100₂ = 100, а для N = 4 (100₂) — 10011₂ = 19.
Укажите минимальное натуральное число N, после обработки которого получается число R, не меньше 500.
В ответе запишите целое число.
Подсказка 1. Запись справа — это либо три последние цифры самой записи, либо двоичная запись числа 3 или 6; поэтому R примерно в 4–8 раз больше N.
Подсказка 2. Проверяйте N подряд, начиная примерно с половины порога: сначала все N делящиеся на 3, затем с остатком 1 и 2.
Подсказка 3. Для N = 61 получается R = 247 (меньше 500), а для N = 62 — R = 502.
Разбор.
Приём — трассировка алгоритма над двоичной записью. Ключевое: дописывание в конец — это умножение на 2^k плюс дописанное число, поэтому R всегда несколько раз больше N. Перебираем N по порядку: для N = 61 получается R = 247 < 500; для N = 62 (111110, остаток 2) получается R = 502 ≥ 500. Значит ответ — 62.
Ответ: 62.
Ответ.
62