У Васи есть доступ к Интернету по высокоскоростному односторон- нему радиоканалу, обеспечивающему скорость получения им инфор-
мации 256 000 бит/с. У Пети нет скоростного доступа к Интернету,
но есть возможность получать информацию от Васи по низкоскорос-
тному телефонному каналу со средней скоростью 32 768 бит/с. Петя
договорился с Васей, что тот будет скачивать для него данные
объёмом 5 Мбайт по высокоскоростному каналу и ретранслировать
их Пете по низкоскоростному каналу. Компьютер Васи может начать
ретрансляцию данных не раньше, чем им будут получены первые
375 Кбайт этих данных. Каков минимально возможный промежуток
времени (в секундах) с момента начала скачивания Васей данных до
полного их получения Петей?
Просто прогоняем бинарный поиск дважды, сначала ищем ближайшее число, не большее нужного, потом не меньшее. Для того, чтобы такие числа были, можно дописать в массив очень большое число и очень маленькое. Затем выбираем из этих двух найденных чисел то, что будет ближе.
Пример реализации:
def bin_search(arr, target, kind="<="):
assert kind in ["<=", ">="]
if kind == "<=":
comp = lambda a, b: a <= b
else:
comp = lambda a, b: a < b
l = 0
r = len(a) - 1
while l < r - 1:
m = (l + r) // 2
if comp(a[m], target):
l = m
else:
r = m
if kind == "<=":
return arr[l]
else:
return arr[r]
def nearest(arr, target):
nearest_le = bin_search(arr, target, "<=")
nearest_ge = bin_search(arr, target, ">=")
if nearest_ge - target < target - nearest_le:
return nearest_ge
else:
return nearest_le
_ = input()
a = [int(x) for x in input().split()]
a = [float("-Infinity")] + a + [float("+Infinity")]
for target in map(int, input().split()):
print(nearest(a, target))
1. .xls - книга Excel
2. .jpg - изображение jpeg
3. .pas - программа на языке Pascal
4. .avi - видео
5. .doc - документ Word
6. .cpp - программа на языке C++
7. .rtf - текстовый документ с форматированием
8. .gif - изображение gif
9. .wav - звуковой файл
10. .txt - текстовый файл
11. zip - архив
12. .java - программа на языке Java
13. .py - программа на языке Python
В комментарии возник вопрос, не являются ли файлы .doc, .xls программами, ведь они могут содержать макросы, написанные на языке VBA.
ответ на этот вопрос скорее нет, чем да. Во-первых, .doc, .xls файлы действительно поддерживают макросы, но это не главное предназначение таких файлов, они могут, но не обязаны содержать программный код (в отличие от собственно тестов программ). С таким же успехом Excel можно было бы называть графическим редактором, ведь в нём можно создавать несложные изображения и открывать и изменять некоторые графические файлы. Во-вторых, .xls, .doc - это контейнеры, примерно такие же, что и .zip, только хранящие текст, картинки, разметку, макросы, и другие интересные вещи. Кстати, новые форматы .xlsx, .docx - и вовсе zip-архивы, открываются архиваторами