Задача к ЕГЭ по информатике на тему «Запись числа в двоичной системе счисления» №1

Алгоритм получает на вход натуральное число $N > 1 » class=»math» src=»/images/inform/quest/quest-2306-1.svg» width=»auto»> и строит по нему новое число <img decoding=$ следующим образом:

Строится двоичная запись числа $N$ .
Вместо последней (самой правой) двоичной цифры дважды записывается вторая слева цифра двоичной записи.
Результат переводится в десятичную систему.

Пример. Дано число $N = 19$ . Алгоритм работает следующим образом:

Двоичная запись числа $N : 10011$ .
Вторая слева цифра $0$ , единица в конце записи заменяется на два нуля, новая запись $100100$ .
Результат работы алгоритма $R = 36$ .

При каком наименьшем числе $N$ в результате работы алгоритма получится R > 92 » class=»math» src=»/images/inform/quest/quest-2306-10.svg» width=»auto»>? В ответе запишите это число в десятичной системе счисления. </p></div>
<p><button class= Показать ответ

for i in range(2, 1000):
    n = bin(i)[2:]
    n = n[:-1] + n[1] * 2
    if int(n, 2) > 92:
        print(i)
        break

Аналитическое решение:

Давайте перебирать числа $R$ , большие, чем $92$ , мы знаем, что получившееся число должно оканчиваться на две одинаковые цифры и эти цифры должны совпадать со второй цифрой слева.

Подойдёт число $9310 = 1011101$ ? Нет, последние две цифры не совпадают.

Подойдёт число $9410 = 1011110$ ? Нет, последние две цифры не совпадают.

Подойдёт число $95 = 1011111 10$ ? Возможно, так как последние две цифры совпадают, но вторая цифра слева — ноль, а значит её не могли дописать два раза и получить $95$ , значит оно не подходит.

Подойдёт число $9610 = 1100000$ ? Возможно, так как последние две цифры совпадают, но вторая цифра слева — единица, а значит её не могли дописать два раза и получить $96$ , значит оно не подходит.

Подойдёт число $9710 = 1100001$ ? Нет, последние две цифры не совпадают.

Подойдёт число $9810 = 1100010$ ? Нет, последние две цифры не совпадают.

Подойдёт число $9910 = 1100011$ ? Возможно, так как последние две цифры совпадают, вторая цифра — единица, и число само заканчивается на две единицы, а значит это число могло быть результатом алгоритма. Значит раньше число выглядело так: $11000X$ , где вместо икса может быть любая цифра, так как две одинаковые цифры записываются ВМЕСТО последней цифры. Значит минимальным числом будет $1100002 = 4810$ .

Ответ: 48