Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Вместо последней (самой правой) двоичной цифры дважды записывается вторая слева цифра двоичной записи.
3. Результат переводится в десятичную систему.
Пример. Дано число N = 19. Алгоритм работает следующим образом:
1. Двоичная запись числа N: 10011.
2. Вторая слева цифра 0, единица в конце записи заменяется на два нуля, новая запись: 100100.
3. Результат работы алгоритма R = 36.
При каком наименьшем числе N в результате работы алгоритма получится R > 76? В ответе запишите это число в десятичной системе счисления.
Число на выходе должно превышать 7610 = 10011002. Заметим, что можно рассматривать только те числа, большие 7610, у которых в двоичной записи на конце стоят либо две единицы, либо два нуля. Также заметим, что для числа 7610 исходными числами могли быть либо 1001102, либо 1001112, ни одно из них нам не подходит, поскольку после работы алгоритма не получится числа,
Таким образом, ответ — 1010002 = 4010.
Ответ: 40.
Приведем другое решение.
Заметим, что в результате применения алгоритма к числам, различающимся только последней цифрой двоичной записи, получаются одинаковые результаты. В остальных случаях большим исходным числам соответствует больший результат. Рассмотрим числа, большие 7610 = 10011002, и выберем наименьшее из них, которое может являться исходным числом N.
7710 = 10011012 — не может являться результатом работы алгоритма.
7810 = 10011102 — не может являться результатом работы алгоритма.
7910 = 10011112 — не может являться результатом работы алгоритма.
8010 = 10100002 — может являться результатом работы алгоритма, может быть получено из числа 1010002 = 4010.
Таким образом, ответ — 1010002 = 4010.
Приведём другое решение на языке Python.
for n in range(2, 100):
s = bin(n)[2:] # перевод в двоичную систему
s = str(s)
t = s[1] * 2
s = s[0:len(s)-1]
s += t
r = int(s, 2) # перевод в десятичную систему
if r > 76:
print(n)
break
Приведём решение Бориса Савельева на языке Python.
a = []
for n in range (4,1000):
if int(bin(n)[2:-1]+bin(n)[2:-1][1]+bin(n)[2:-1][1],2) > 76:
a.append(n)
print(min(a))