Question

Вася, решая одно из заданий ЕГЭ, вычисляет значение функции для всех чисел в диапазоне от 0 до 16777215. Компьютер Васи получает каждое значение за 1 мс. Подпольный пиратский квантовый компьютер «Мегатрон» может обработать все эти вычисления одновременно. Но так как он подпольный и пиратский, то постоянно делает ошибки в тех числах, двоичная запись которых содержит две единицы подряд, и их приходится обрабатывать каждое по отдельности. На сколько мс «Мегатрон» опередит в вычислениях Васю, если ему на вычисление функции для каждого числа (или одновременного вычисления функции для возможных значений) требуется также 1 мс? Ответ запишите числом без дополнительных пробелов и символов до и после (например: 18101150).
Срочно!​

Answer 1

Ответ:

25 милисекунд.

Объяснение:

Если 16777215 x значений обрабатываются одновременно, и каждое значение нахождается за 1мс, то если бы у Мегатрона не был баг насчёт бинарных чисел с единицами больше 2 (назовём такие числа O), то Мегатрон напечатал бы все значения одновременно за 1мс, значит на 16777214 мс быстрее чем компьютер Васи, но из за бага, приходится тратить дополнительную 1мс на каждое число O, а таких чисел много в диапазоне [0, 16777215].

Напишем код (python), где в данном диапазоне добавляется одна секунда, когда встречается число O, чтобы баг работал и замедлял Мегатрон:

seconds=0

def hasTwoUnits(number):

   ones = 0

   for i in range(len(number)):

       if number[i]=="1": ones+=1

   if (ones>=2): return True

for i in range(0, 16777216):

   binary = str(format(i, "b"))

   if hasTwoUnits(binary): seconds+=1

   

print("seconds: ", seconds)

Результат — 16777191 милисекунд.

Значит в диапазоне  [0, 16777215] есть только 25 чисел(16777215-16777191), у которых меньше 2 единицы в бинарном виде.

Значит разница между скоростями Мегатрона и компьютера Васи — 25 мс (в пользу Мегатрона).