Задание 5 ЕГЭ по информатике: алгоритм, который строит новое число

Задание 5 ЕГЭ по информатике описывает алгоритм: по числу N строится его двоичная или троичная запись, к ней по правилу дописываются цифры, и получается новое число R. Нужно найти наименьшее N или R с заданным свойством; надёжнее всего перебрать N короткой программой.

Как решать

Алгоритм в задании 5 состоит из трёх шагов: построить запись числа N в двоичной (иногда троичной) системе, изменить её по правилу и перевести результат R обратно в десятичную систему. Спрашивают обычно наименьшее N, при котором R больше заданного числа, или наименьшее R, большее заданного.

Шаг 1. Разберите пример из условия вручную: переведите N, примените правило и сравните с R из условия. Так вы убедитесь, что правило понято верно, особенно с какой стороны дописываются цифры.

Шаг 2. Запишите алгоритм функцией на Python. Двоичную запись даёт bin(n)[2:], обратный перевод — int(s, 2). Троичную запись строят делением на 3 с остатком, обратный перевод — int(s, 3).

Шаг 3. Переберите N подряд. Если спрашивают наименьшее N, остановитесь на первом подходящем. Если спрашивают наименьшее R, переберите N с запасом и возьмите минимум среди подходящих R: результат растёт вместе с N неравномерно.

Вручную задачу решают оценкой длины записи. Если правило дописывает к записи k цифр, R примерно в 2^k раз больше N (в троичной системе — в 3^k раз), и нужный диапазон N находится за пару шагов. Программа всё равно полезна для проверки: ошибка в одной цифре меняет ответ.

Примеры с решением

Пример 1

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R так:

Например, для N = 5 = 101₂ единиц две, запись становится 101010₂ и R = 42; для N = 4 = 100₂ единица одна, запись 111001₂ и R = 57.

Укажите наименьшее число N, для которого R больше 230.

Проверка ответа на Python

def R(n):
    b = bin(n)[2:]  # двоичная запись без префикса 0b
    if b.count("1") % 2 == 0:
        b = "10" + b + "0"
    else:
        b = "11" + b + "1"
    return int(b, 2)


n = 1
while R(n) <= 230:
    n += 1
print(n)

Ответ: 19

Если в записи N четыре цифры (N ≤ 15), в записи R семь цифр и R ≤ 127. При N от 16 до 31 запись R восьмизначная. Когда единиц чётное число, R начинается с 10 и не больше 191.

Когда единиц нечётное число, R = 11 + запись N + 1, то есть R = 225 + 2 · (N − 16). Условие R > 230 выполняется при N ≥ 19, если у N нечётное число единиц.

N = 19 = 10011₂: единиц три, R = 11100111₂ = 231. Числа 16, 17 и 18 дают 225, 162 и 164. Ответ: 19.

Пример 2

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R так:

Например, для N = 6 = 20₃ получается 2020₃ = 60; для N = 5 = 12₃ остаток равен 2, 2 · 4 = 8 = 22₃, запись 1222₃ и R = 53.

Укажите наименьшее число R, большее 300, которое может получиться в результате работы алгоритма. Ответ запишите в десятичной системе.

Проверка ответа на Python

def ternary(n):
    s = ""
    while n > 0:
        s = str(n % 3) + s
        n //= 3
    return s


def R(n):
    s = ternary(n)
    if n % 3 == 0:
        s = s + s[-2:]
    else:
        s = s + ternary(n % 3 * 4)
    return int(s, 3)


# R растёт примерно как 9·N, поэтому N до 1000 заведомо хватает
print(min(R(n) for n in range(1, 1000) if R(n) > 300))

Ответ: 303

В обоих случаях к записи дописываются две троичные цифры, поэтому R = 9 · N + t, где t — значение дописанных цифр: от 0 до 8.

При N ≤ 32 получается R ≤ 9 · 32 + 8 = 296. N = 33 = 1020₃ делится на 3, дописываются цифры 20, запись 102020₃ = 303. При N ≥ 34 уже R ≥ 306.

Ответ: 303.

Типичные ошибки

Потренироваться на тренажёре

Частые вопросы

Как перевести число в двоичную систему на Python?

bin(n) возвращает строку вида 0b101, поэтому берут bin(n)[2:]. Строку из двоичной системы в число переводит int(s, 2). Для других оснований запись строят циклом с делением и остатком.

Можно ли решить задание 5 без программы?

Да, оценкой длины записи и разбором нескольких соседних N, как в примерах выше. Программа из 8–10 строк проверяет ответ и защищает от ошибки в одной цифре.

Сколько баллов дают за задание 5?

1 первичный балл. Уровень сложности базовый, время по спецификации — около 4 минут.

Официальные материалы

Другие задания

Все задания и структура экзамена — на странице ЕГЭ по информатике. Соседние разборы: задание 4 и задание 6.

Описание задания сверено 28 сентября 2026 года со спецификацией 2027 года (документы 2027 года). Примеры составлены нами по структуре демоверсии, каждое решение запущено, и напечатанный им ответ совпадает с ответом на странице. Кодолимп не связан с разработчиками экзамена. Заметили неточность — напишите нам.