1 Ответ
Задание 1. Рекламные паузы
Слон Семён включил в онлайн‑кинотеатре новый фильм «Матрица». После каждых a минут показа фильма вставляется реклама длиной b минут. Но если в момент планируемого начала рекламного блока фильм завершается, то рекламу не показывают.
Фильм без рекламы длится nn минут. Сколько времени займёт показ всего фильма вместе с рекламой?
Задание 2. Популярный пост
В новом мессенджере «Дружба» разработчики предусмотрели возможность оставить реакцию под сообщением. Каждый пользователь может оставить даже две разные реакции, но больше двух реакций выбрать нельзя. Под некоторым сообщением пользователи оставили aa реакций «Согласен», b реакций «Не согласен» и c реакций «Забавно». Какое минимальное количество пользователей могло отреагировать на данное сообщение?
В первой строке входных данных записано число aa, во второй b, в третьей c из условия задачи (0⩽a, b, c⩽7⋅108)
Выведите единственное число: минимально возможное количество пользователей, оставивших реакции под сообщением.
Если результат получится больше чем 1234554321, нужно вывести число -1.
В примере из условия два пользователя могли поставить реакции первого и третьего типов, третий пользователь поставил реакцию второго и третьего типов, а четвёртый пользователь только реакцию третьего типа.
Задание 3. Встреча у фонтана
Маша и Паша живут на одной улице, и их дома разделены только парком, в котором друзья любят гулять. В центре парка есть красивый фонтан, у которого Маша и Паша хотят сегодня встретиться. Известно, что Маша идёт до фонтана mm минут, Паша p минут.
Выйти из домов они договорились одновременно, также друзья решили приходить к фонтану и, если там никого нет, идти обратно к дому, а затем снова разворачиваться, пока в итоге не случится встреча у фонтана.
Помогите друзьям понять, смогут ли они встретиться в парке у фонтана, и если да, то сколько минут пройдёт с момента выхода из домов до их встречи.
Первая строка содержит целое число m (1⩽m⩽109) время в минутах, которое требуется Маше, чтобы дойти от дома до фонтана.
Вторая строка содержит целое число p (1⩽p⩽109) время в минутах, которое требуется Паше, чтобы дойти от дома до фонтана.
Выведите одно целое число время, через которое Маша и Паша смогут встретиться у фонтана, если выйдут из домов одновременно, или -1, если этого никогда не случится.
Обратите внимание на то, что значение ответа в этой задаче может превышать возможное значение 32‑битной целочисленной переменной, поэтому необходимо использовать 64 битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Задание 4. Раскраска стены
Длина кирпича в два раза больше его высоты, то есть его можно представить как прямоугольник размером 1 х 2 клетки. Стена сложена из n рядов кирпичей, каждый ряд состоит из т клеток, в любом ряду последовательность кирпичей сдвинута на 1 клетку по сравнению с вышележащим и нижележащим. То есть в каждом ряду может быть не более — целых кирпичей, а в концах каждого ряда могут находиться половинки кирпичей.
При этом в самом нижнем ряду слева лежит целый кирпич.
На картинке приведён пример стены для n = 4 и т = 7.
Ответ:
import sys
def main():
data = sys.stdin.read().split()
if not data:
return
n = int(data[0])
m = int(data[1])
brick_id = [[0] * m for _ in range(n)]
next_id = 1
for i in range(n):
if i % 2 == 0:
j = 0
while j < m:
if j + 1 < m:
brick_id[i][j] = next_id
brick_id[i][j+1] = next_id
next_id += 1
j += 2
else:
brick_id[i][j] = next_id
next_id += 1
j += 1
else:
j = 0
if j < m:
brick_id[i][j] = next_id
next_id += 1
j += 1
while j < m:
if j + 1 < m:
brick_id[i][j] = next_id
brick_id[i][j+1] = next_id
next_id += 1
j += 2
else:
brick_id[i][j] = next_id
next_id += 1
j += 1
total_bricks = next_id — 1
graph = {}
for i in range(1, total_bricks + 1):
graph[i] = set()
for i in range(n):
for j in range(m):
current = brick_id[i][j]
if j + 1 < m:
right = brick_id[i][j+1]
if current != right:
graph[current].add(right)
graph[right].add(current)
if i + 1 < n:
bottom = brick_id[i+1][j]
if current != bottom:
graph[current].add(bottom)
graph[bottom].add(current)
colors = {}
for id in range(1, total_bricks + 1):
used_colors = set()
for neighbor in graph[id]:
if neighbor in colors:
used_colors.add(colors[neighbor])
color = 1
while color in used_colors:
color += 1
colors[id] = color
for i in range(n):
line = ».join(str(colors[brick_id[i][j]]) for j in range(m))
print(line)
f __name__ == ‘__main__’:
main()
Задание 5. Проблемы логистики
Подготовка к заключительному этапу всероссийской олимпиады школьников по информатике 3025 года идёт полным ходом. Уже готовы и набор задач, и разборы к ним. Единственное, что осталось сделать, — настроить компьютеры, на которых участники будут писать олимпиаду. Но сперва устройства надо доставить к месту проведения.
Число участников заключительного этапа ВсОШ 3025 сильно увеличилось по сравнению с предыдущими годами, поэтому компьютеров необходимо много. Все они уже разложены по пі контейнерам, 1-й из которых весит 1; килограммов. Задачу доставки этих контейнеров поручили транспортной компании, у которой (по счастливой случайности) есть ровно пі машин, причём стоимость провоза одного килограмма груза на j-й из машин равна P; рублей. Таким образом, стоимость перевоза контейнера номер і на машине номер ј равна wi — Рі рублей. В одной машине можно перевозить только один контейнер! Сейчас перед менеджерами транспортной компании стоит задача распределения
контейнеров по машинам. Стоимость перевозки одного контейнера не должна превышать к рублей (иначе перевозку сочтут неоптимальной), но при этом менеджеры хотят максимизировать суммарную стоимость перевозки всех контейнеров. Помогите им: найдите максимально возможную суммарную стоимость.
Ответ:
import bisect
class SegmentTree:
def __init__(self, data):
self.n = len(data)
self.data = data
self.size = 1
while self.size < self.n:
self.size *= 2
self.tree = [-1] * (2 * self.size)
self.index_tree = [-1] * (2 * self.size)
for i in range(self.n):
self.tree[self.size + i] = self.data[i]
self.index_tree[self.size + i] = i
for i in range(self.n, self.size):
self.tree[self.size + i] = -1
self.index_tree[self.size + i] = -1
for i in range(self.size — 1, 0, -1):
left_val = self.tree[2 * i]
right_val = self.tree[2 * i + 1]
if left_val >= right_val:
self.tree[i] = left_val
self.index_tree[i] = self.index_tree[2 * i]
else:
self.tree[i] = right_val
self.index_tree[i] = self.index_tree[2 * i + 1]
def update(self, index):
i = self.size + index
self.tree[i] = -1
self.index_tree[i] = -1
i //= 2
while i:
left_val = self.tree[2 * i]
right_val = self.tree[2 * i + 1]
if left_val >= right_val:
self.tree[i] = left_val
self.index_tree[i] = self.index_tree[2 * i]
else:
self.tree[i] = right_val
self.index_tree[i] = self.index_tree[2 * i + 1]
i //= 2
def query(self, l, r):
l += self.size
r += self.size
res_val = -1
res_idx = -1
while l <= r:
if l % 2 == 1:
if self.tree[l] > res_val:
res_val = self.tree[l]
res_idx = self.index_tree[l]
l += 1
if r % 2 == 0:
if self.tree[r] > res_val:
res_val = self.tree[r]
res_idx = self.index_tree[r]
r -= 1
l //= 2
r //= 2
return (res_val, res_idx)
def main():
import sys
data = sys.stdin.read().split()
if not data:
return
n = int(data[0])
k = int(data[1])
w = list(map(int, data[2:2+n]))
p = list(map(int, data[2+n:2+2*n]))
w_desc = sorted(w, reverse=True)
p_asc = sorted(p)
for i in range(n):
if w_desc[i] * p_asc[i] > k:
print(-1)
return
st = SegmentTree(p_asc)
total = 0
for weight in w_desc:
threshold_int = k // weight
j = bisect.bisect_right(p_asc, threshold_int) — 1
if j < 0:
print(-1)
return
val, idx = st.query(0, j)
if val == -1:
print(-1)
return
total += weight * val
st.update(idx)
print(total)
if __name__ == ‘__main__’:
main()