ЕГЭ 5 · Формальное исполнение алгоритма
Преобразование двоичной записи
Автомат обрабатывает натуральное число N (0≤N≤255) по следующему алгоритму:
1) Строится восьми битная двоичная запись числа N.
2) Удаляются средние 4 цифры.
3) Полученное число переводится в десятичную запись и выводится на экран.
Какое наибольшее число, меньшее 110, после обработки автоматом даёт результат 7?
Подсказка
Сначала выполните все шаги для одного N, сохраняя строку после каждого изменения. Затем уточните, что требуется выбрать: N, R или количество значений.
Идея решения
Искомая величина: Какое наибольшее число, меньшее 110, после обработки автоматом даёт результат 7?
Разделите решение на два действия: для одного входного числа точно воспроизведите алгоритм, затем отберите результаты по условию задачи. Храните запись числа строкой; основание используемой системы счисления — 2.
Удаление разрядов выполняйте срезом строки со стороны, указанной в условии. После удаления числовое значение остатка записи вычисляется заново; ведущие нули не увеличивают это значение.
После завершения всех преобразований получите числовой результат: R = int(s, 2). Ограничения на величину R проверяйте численно: лексикографический порядок строк не совпадает с порядком чисел.
Отбирайте ту величину, о которой спрашивается в последнем предложении: исходное число и результат алгоритма нельзя подменять друг другом. Для наименьшего входа рассматривайте допустимые N по возрастанию; для наибольшего проверяйте весь обоснованный диапазон.
Строгое «больше» означает >, а «не меньше» — >=; аналогично различайте верхние границы. Диапазон перебора определяйте из ограничений и изменения длины записи, а не произвольной константой. Пример из условия помогает проверить отдельный проход алгоритма.
Ответ: 107.