Страница: 1 Отображать по:

#113549

Серверы на Меркурии

Темы: [Динамическое программирование]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2017, 2 день, Серверы на Меркурии ]

Компьютерная система управления станциями на Меркурии состоит из n серверов, пронумерованных от 1 до n. Серверы соединены (n - 1) двусторонними каналами связи, i-й из которых соединяет i-й и (i + 1)-й серверы.

С Земли необходимо передать пакет обновления программного обеспечения для компьютерной системы управления. Пакет необходимо установить на каждый сервер. Стоимость передачи пакета обновления с Земли на Меркурий очень высока, поэтому с Земли пакет обновления передаётся только на один сервер. Затем пакет необходимо передать на все остальные серверы по каналам связи, возможно, через другие серверы.

Из-за высокой солнечной радиации на Меркурии передавать пакет обновления по каналам связи можно только в некоторые промежутки времени. Для i-го канала связи известен промежуток времени [l_i, r_i], во время которого возможна передача пакета по этому каналу. Пакет передаётся по любому каналу связи мгновенно.

Пакет обновления, переданный на j-й сервер, немедленно устанавливается и помещается в специальный буфер памяти, из которого он может быть передан на другие серверы. Пакет находится в буфере памяти j-го сервера в течение t_j секунд с момента его получения. Если в момент нахождения пакета в буфере памяти сервера появляется возможность передать его по каналу связи на соседний сервер, на котором пакет обновления пока не установлен, то он немедленно передаётся по этому каналу связи.

Поскольку пакет содержит важные обновления, требуется начать его распространение как можно раньше.

Требуется написать программу, которая для всех i от 1 до n определяет, возможно ли установить пакет обновления на все серверы, передав его с Земли на i-й сервер. Если это возможно, то необходимо определить, в какой минимальный неотрицательный момент времени можно установить пакет на этот сервер, чтобы в результате обновление оказалось установлено на всех серверах.

Входные данные

Первая строка входных данных содержит n — количество серверов (1 ≤ n ≤ 200 000).

Вторая строка содержит n целых чисел t₁, t₂, ..., t_n, где t_j — время нахождения пакета в буфере памяти j-го сервера (0 ≤ t_j ≤ 10⁹).

Следующие (n - 1) строк описывают каналы связи. Для описания i-го канала задаются два целых числа l_i и r_i — границы промежутка времени, на протяжении которого возможна передача пакета по этому каналу (0 ≤ l_i ≤ r_i ≤ 10⁹).

Выходные данные

Выходные данные должны содержать n целых чисел a₁, a₂, ..., a_n.

Число a_i должно быть равно такому минимальному неотрицательному моменту времени, что при установке пакета обновления на i-й сервер в момент a_i, пакет будет в итоге установлен на всех серверах. Если такого момента времени для i-го сервера не существует, необходимо вывести a_i = - 1.

Примечание

В первом примере имеется всего один сервер, минимальное подходящее время, в которое можно установить на него обновление — 0.

Во втором примере есть два сервера, передать обновление между которыми можно в промежуток от 6 до 8. Первый сервер хранит обновление в буфере 3 единицы времени, а второй — 5 единиц времени. Если отправить обновление первому серверу в момент 3, то он передаст его второму серверу в момент 6. Аналогично если отправить обновление второму серверу в момент 1, то он передаст его первому серверу в момент 6.

В третьем примере нельзя передать обновление первому серверу так, чтобы оно передалось третьему серверу, так как канал 2–3 закрывается до того, как открывается канал 1–2. Можно отправить обновление второму или третьему серверу в момент 5. В этот момент канал 2–3 открыт, поэтому его сразу получат второй и третий серверы. В момент 7, когда откроется канал 1–2 обновление ещё будет находиться в буфере второго сервера, и передастся первому серверу.

В четвёртом примере второй сервер хранит пакет 0 единиц времени, а канал 2–3 открыт в промежуток 5–5. Чтобы передать обновление через второй сервер к третьему серверу, оно должно попасть ко второму серверу в момент 5. Если же мы хотим отправить обновление третьему серверу, то это можно сделать в момент 4, при этом оно будет храниться до момента 7 и будет в итоге установлено на все серверы.

Примеры

Входные данные

1
10

Выходные данные

Входные данные

2
3 5
6 8

Выходные данные

3
1

Входные данные

Выходные данные

-1
5
5

Входные данные

Выходные данные

#113550

Антивещество

Темы: [Динамическое программирование] [Дерево отрезков, RSQ, RMQ] [Система непересекающихся множеств] [Разреженные таблицы (sparse table)]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2017, 2 день, Антивещество ]

Компания тестирует технологию получения антивещества, используемого в качестве топлива в межпланетном звездолёте. Антивещество получается в результате специальных экспериментов в реакторе.

Известно n типов экспериментов, приводящих к получению антивещества. В результате проведения эксперимента i-го типа в выходной контейнер реактора добавляется от l_i до r_i граммов антивещества. Из соображений безопасности запрещается накапливать в контейнере более a граммов антивещества.

Затраты на проведение эксперимента i-го типа составляют c_i, а стоимость одного грамма полученного антивещества составляет 10⁹.

Если после проведения экспериментов в контейнере образовалось t граммов антивещества, а суммарные затраты на проведение экспериментов в реакторе составили s, то прибыль определяется по формуле (t·10⁹ - s). Компании необходимо разработать стратегию проведения экспериментов, позволяющую максимизировать прибыль, которую можно гарантированно получить.

В зависимости от результатов предыдущих экспериментов стратегия определяет, эксперимент какого типа следует провести, или решает прекратить дальнейшее выполнение экспериментов. Стратегия позволяет гарантированно получить прибыль x, если при любых результатах проведения экспериментов: во-первых, в контейнере реактора оказывается не более a граммов антивещества, во-вторых, прибыль составит не менее x.

Например, пусть возможен только один тип эксперимента, порождающий от 4 до 6 граммов антивещества, затраты на его проведение равны 10, а вместимость контейнера составляет 17 граммов. Тогда после двукратного проведения эксперимента в контейнере может оказаться от 8 до 12 граммов антивещества. Если получилось 12 граммов, то больше проводить эксперимент нельзя, так как в случае получения 6 граммов антивещества контейнер может переполниться. В остальных случаях можно провести эксперимент в третий раз и получить от 12 до 17 граммов антивещества. В худшем случае придётся провести эксперимент трижды, затратив в сумме 30, прибыль составит (12·10⁹ - 30) = 11 999 999 970.

Требуется написать программу, которая определяет максимальную прибыль x, которую гарантированно можно получить.

Входные данные

Первая строка входных данных содержит два целых числа: n — количество типов экспериментов и a — максимально допустимое количество антивещества в контейнере (1 ≤ n ≤ 100, 1 ≤ a ≤ 2 000 000).

Следующие n строк содержат по три целых числа l_i, r_i и c_i — минимальное и максимальное количество антивещества, получаемое в результате эксперимента типа i, и затраты на эксперимент этого типа, соответственно (1 ≤ l_i ≤ r_i ≤ a, 1 ≤ c_i ≤ 100).

Выходные данные

Выходные данные должны содержать одно целое число — максимальную прибыль x, которую гарантированно можно получить.

Примеры

Входные данные

1 17
4 6 10

Выходные данные

11999999970

Входные данные

2 11
2 2 100
3 5 5

Выходные данные

9999999890

Страница: 1 Отображать по:

Выбрано

Отменить

Добавить в контест