Чай [python]
имя входного файла: tea.in или стандартный поток ввода
имя выходного файла: tea.out или стандартный поток вывода
ограничение времени: 1 с
ограничение памяти: 256m
петя любит и информатику, поэтому он решил начать готовиться к сразу по обоим предметам. для этого он составил расписание, которое выглядит так: сначала петя a дней готовится к по , затем b дней к по информатике, потом опять a дней готовится к по и т.д. также петя знает, что когда он занимается , он должен выпивать в день ровно c чашек чая, а в день занятий по информатике — d чашек.
решив начать готовиться с новой недели, петя захотел узнать, сколько ему нужно сделать запасов чая на n недель, которые остались до начала самых важных олимпиад. напишите программу, которая определяет сколько всего чашек чая выпьет петя за целое число недель n.
формат входных данных
в первой строке дается целое число
a (1≤a≤1000) — количество подряд идущих дней, которые петя тратит на подготовку к .
во второй строке дается целое число b (1≤b≤1000) — количество подряд идущих дней, которые петя тратит на подготовку к информатике.
в третьей строке дается целое число c (1≤c≤500) — количество чашек чая, которые будет в день пить петя во время подготовки к .
в четвертой строке дается целое число d (1≤d≤500) — количество чашек чая, которые будет в день пить петя во время подготовки к информатике.
в пятой строке дается целое число n (1≤n≤500) — количество недель подготовки пети.
формат результата
выведите одно число — сколько всего чашек чая выпьет петя за
n недель.
примеры
входные данные
3
4
1
1
1
результат работы
7
входные данные
1
2
3
4
2
результат работы
51
Просто прогоняем бинарный поиск дважды, сначала ищем ближайшее число, не большее нужного, потом не меньшее. Для того, чтобы такие числа были, можно дописать в массив очень большое число и очень маленькое. Затем выбираем из этих двух найденных чисел то, что будет ближе.
Пример реализации:
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))