Решение от результата

Вместо перебора N можно перебирать результаты: брать R от границы вверх, записывать в двоичной системе и проверять, мог ли алгоритм его выдать. Так решают задачу темы без программы — нужен только перевод чисел.

Алгоритм дописывает 10 к чётному N и 01 к нечётному. Значит, у подходящего R запись оканчивается на 10 или 01, а оставшаяся слева часть — запись N нужной чётности.

Наименьший результат больше 150 — 154 при N = 38. Здесь справа всегда дописываются две цифры, поэтому больший N даёт больший R, и наименьшему R соответствует наименьшее N: ответ 38, как и в подтеме 4.

Иногда удобнее идти от результата обратно к исходному числу. Если алгоритм сохраняет запись N и дописывает справа две цифры, то запись R без двух последних цифр — это запись N, а две последние цифры — дописанный блок.

Возьмём алгоритм с двумя последовательными проверками суммы цифр и проверим, может ли он выдать R = 100. 100 = 1100100₂. Разделяем запись: 11001 | 00. Предполагаемый вход 11001₂ = 25. У числа 25 три единицы. Значит, по алгоритму нужно дописать 10, а не 00. Следовательно, 100 получить нельзя.

Проверим 102 = 1100110₂. Разделяем: 11001 | 10. Вход снова равен 25, хвост правильный. Значит, 102 получить можно.

Удаление хвоста находит предполагаемый вход. Затем всё равно нужно проверить, что алгоритм действительно создаёт именно такой хвост. Одного подходящего окончания результата недостаточно: оно должно согласовываться с исходной частью.

• Обратный ходперебираем R от границы и проверяем, мог ли он получиться
• Хвост записидолжен совпасть с тем, что алгоритм дописывает
• Остаток слеваэто N; его свойство (чётность, сумма цифр) проверяют
• R растёт с Nтогда наименьшему R соответствует наименьшее N