Нужно найти максимальное значение R < 170. Поэтому проверяем возможные результаты по убыванию: 169, 168, 167, 166, …
Возможны три способа получить хвост. Если N делится на 3, копируются последние три разряда N. При остатке 1 дописывается 11₂, а при остатке 2 — 110₂.
169 = 10101001₂. Окончание 001 не равно ни 11, ни 110. После снятия трёх битов получаем N = 10101₂ = 21. Число 21 делится на 3, поэтому должны копироваться его последние три бита — 101. Но у кандидата стоит 001. Значит, 169 невозможно.
Для 168 после снятия трёх битов снова получаем N = 21, но у кандидата хвост 000 вместо нужного 101. Поэтому 168 также невозможно.
Для 167 = 10100111₂ нужно проверить два варианта.
Если снять 11, получаем N = 101001₂ = 41. Но 41 mod 3 = 2, поэтому должен дописываться хвост 110, а не 11.
Если снять три последние цифры 111, получаем N = 10100₂ = 20. Число 20 не делится на 3, значит копирование запрещено. При остатке 2 правильный хвост — 110, поэтому из N = 20 получилось бы 166.
Проверяем 166:
166 = 10100110₂.
Снимаем хвост 110:
N = 10100₂ = 20.
Остаток от деления 20 на 3 равен 2:
2 · 3 = 6 = 110₂.
Значит, хвост 110 действительно должен быть приписан:
10100 | 110 = 10100110₂ = 166.
166 получить можно, а 167, 168 и 169 — нельзя. Следовательно, максимальный результат меньше 170 равен 166.
Ответ: 166.