Задание 5 ЕГЭ по информатике: формальное исполнение алгоритма

Под разными формулировками в банке скрывается один и тот же каркас из трёх шагов:

1. Число $N$ переводится из десятичной записи в другую систему счисления — чаще всего двоичную, реже троичную или четверичную.
2. Полученная запись обрабатывается по правилу, которое обычно ветвится на 2 случая (иногда на 4): приписать цифры слева, справа или в середину; заменить первые/последние разряды; заменить каждый разряд на несколько других. Условие ветвления — чётность самого числа, остаток от деления на небольшое число, чётность суммы цифр записи.
3. Получившаяся запись объявляется двоичной (троичной, четверичной) записью числа $R$, и $R$ переводится обратно в десятичную.

Циклов и рекурсии здесь нет: правило применяется один или два раза и всё. Сложность не в логике, а в том, чтобы не ошибиться на переводах систем счисления и не перепутать разряды при редактировании записи.

Прежде чем искать приём для больших чисел, обязательно прогоните алгоритм вручную на нескольких маленьких $N$ и сведите шаги в таблицу — так опечатка в правиле обнаруживается сразу, а не после десяти минут поиска. Возьмём правило «чётное число — слева приписывается 10, нечётное — слева приписывается 1 и справа 01» и построим трассировку для $N = 1 \dots 6$:

Уже на этой маленькой таблице видно главное наблюдение задания 5: $R$ растёт не монотонно и не пропорционально $N$ — у нечётных чисел запись длиннее на три разряда, у чётных на два, поэтому «соседние» по величине $N$ могут давать очень разные $R$. Именно из-за этого перебор с единицы вручную ненадёжен, а нужен приём из следующего блока.

Искомое $N$ в заданиях банка бывает и 65, и 273 — перебирать вручную от единицы до трёхзначного числа на экзамене некогда, и почти гарантированно собьётесь со счёта. Правильный ход — обратный: не «перебираем $N$ — вдруг подойдёт», а «понимаем, каким должен быть результат $R$, и возвращаемся к $N$».

Шаги приёма

1. Определите, сколько разрядов должно быть в двоичной записи $R$, чтобы выполнялось условие. Для этого сравните порог из условия с ближайшими степенями двойки: например, порог 516 лежит между $2^9 = 512$ и $2^{10} = 1024$, значит запись $R$ из девяти разрядов заведомо мала ($R \le 511$), а нужной длины — минимум десять разрядов.
2. Зная, на сколько разрядов правило удлиняет запись (это число вы уже нашли в теоретическом блоке 1 — обычно оно разное для чётных и нечётных $N$), вычтите эту длину из нужной длины $R$ и получите минимальную длину записи $N$ для каждого случая ветвления.
3. Возьмите наименьшее число нужной длины в каждой ветке (например, наименьшее семиразрядное нечётное число) — это и есть кандидат, а не число 1.
4. Примените правило к кандидату по-настоящему и убедитесь, что условие правда выполняется: длины разрядов достаточно для превышения по разрядам, но конкретное значение может оказаться и меньше порога — тогда берите следующее число той же длины.
5. Сравните кандидатов из всех веток ветвления (для чётных и нечётных отдельно) и выберите наименьший.

Этот приём не заменяет проверку — он лишь резко сужает область перебора: вместо «попробовать все числа от 1 до 300» вы проверяете 2–4 кандидата на границе. Полный разбор с числами — в примере 1 ниже.

Самое частое непонимание в задании 5 — недооценка того, насколько сильно меняет число дописывание цифры справа. В позиционной системе с основанием $b$ дописать одну цифру $d$ справа к числу $x$ — это не «прибавить $d$», а:

А если справа дописываются две цифры $d_1 d_2$ подряд, число умножается на $b^2$, а не на $b$:

Для двоичной системы ($b = 2$) это значит: приписать один бит справа — $2x + d$, приписать два бита справа — $4x + d_1 \cdot 2 + d_2$. Именно на этой формуле держится второй пример разбора ниже: там правило дважды приписывает по одному биту справа, и в сумме это $R = 4N + 2p$ — без единого перебора.

Важно: это правило работает только для приписывания справа. Приписывание слева устроено иначе — оно не умножает $x$, а меняет его старшие разряды и почти всегда сильнее всего влияет на длину записи, а не на арифметику самого $x$. Не путайте эти два случая: если в условии написано «слева», формула $x \cdot b + d$ не применяется вообще, а нужен приём из блока 3 (анализ длины записи).

КЕГЭ сдаётся за компьютером, и среда программирования (Python, C++, Pascal, Java, C#) доступна на протяжении всего экзамена — не только для заданий с прикреплённым файлом. Задание 5 не требует спец. ПО по инструкции, но ничто не мешает буквально повторить шаги алгоритма из условия в коде и перебрать $N$ в цикле. Это надёжнее ручной трассировки на больших числах и почти не требует дополнительного времени.

Шаблон: переведите правило из условия построчно

def alg(n):
    b = bin(n)[2:]
    if n % 2 == 0:
        b = '10' + b
    else:
        b = '1' + b + '01'
    return int(b, 2)

print(min(n for n in range(1, 100000) if alg(n) > 516))

Запустив этот код, получаем $65$ — тот же ответ, что и приёмом «с конца» в примере 1 ниже. Если вопрос задан про $R$, а не $N$, опишите функцией правило из своего варианта и переберите множество значений $R$. Например, для правила «каждый разряд заменяется двумя: 0 → 00, 1 → 11» (четвёртая формулировка из списка выше) код выглядит так:

def alg(n):
    return int(''.join(c * 2 for c in bin(n)[2:]), 2)

print(min(r for r in {alg(n) for n in range(1, 100)} if r > 63))

Запустив этот код, получаем $192$ — тот же ответ, что и в эталоне банка для этого задания. Обратите внимание: функция $\texttt{alg}$ здесь другая, чем в первом шаблоне, — под каждое правило из условия пишется своя функция, копировать чужую нельзя.

Практический совет: берите верхнюю границу перебора «с запасом» (100–1000 для $N$, редко больше 1000 — числа в этом задании банка не бывают многозначными), это надёжнее, чем пытаться заранее вычислить точную границу. Код короче трассировки на бумаге и не ошибается в переносе разрядов.

День 1–2: разберите 5–7 заданий на маленьких числах, строя полную таблицу трассировки (как в теоретическом блоке) для $N = 1 \dots 10$ — это ставит привычку сверяться с примером из условия. День 3–4: потренируйтесь отдельно определять, на сколько разрядов удлиняется запись в каждой ветке правила — это число нужно для следующего шага. День 5–7: решите 10–15 заданий на числа среднего размера (двух- и трёхзначные ответы), каждый раз явно выписывая формулу приписывания как $x \cdot b + d$, если приписывание идёт справа.

День 1–3: отработайте приём «стройте ответ с конца» на заданиях с трёх- и четырёхзначными ответами — сначала оцените нужную длину записи $R$, затем длину $N$, и только потом проверяйте конкретные числа. День 4–5: напишите и запустите шаблон полного перебора на Python для 5–10 разных правил из банка — это лучшая проверка того, что вы верно разобрали все ветки условия. День 6–7: решайте задания на время без подглядывания в решение и сверяйте себя в тренажёре на заданиях из банка ФИПИ.