Легенда

Сетевая компания «Энергия хаоса» собирается модернизировать оснащение одной из своих подсетей. Эта сеть имеет вид дерева, состоящего из подстанций и просьюмеров. Каждый просьюмер обладает индивидуальным суточным паттерном потребления и генерации (для простоты даны средние значения на каждый час). Просьюмеры подключаются к подстанциям. Подстанции не обладают собственной мощностью, но занимаются диспетчеризацией мощностей с дочерних узлов (в т.ч. других подстанций), а именно: подстанция самостоятельно балансирует мощности дочерних узлов, после чего запрашивает недостающую мощность из внешней для себя сети или передаёт туда избыточную через входную линию, направленную к корню дерева, а именно главной подстанции. Входная линия главной подстанции ведёт к внешнему поставщику.

Для модернизации подстанций специалистам необходимо вычислить максимальную абсолютную мощность, которая проходит через входную линию подстанции в течение суток. Напишите программу, выполняющую этот расчёт для всех подстанций сети.

Входной формат: два списка. Первый — список паттернов мощностей узлов. Индекс в этом списке соответствует номеру узла (нумерация с 0). Для подстанций вместо графика записан None, для остальных узлов — список из 24 вещественных чисел, мощности узла в определённый час суток (положительное число — генерация, отрицательное — потребление). Второй — список рёбер дерева (до 64), представленных неупорядоченными парами номеров узлов (которые соответствуют индексу в первом списке). Главная подстанция имеет индекс 0. Все эти данные представлены в виде строки, которую можно проинтерпретировать командой eval. Пример входных данных:

([None, [-12,-11,-10,-9.5,-8,-7,-6,-5,-4,-3,-2,-1,1,2,3,4,5,6,7,8,9.5,10,11,12], 
None, [-12,-11,-10,-9.5,-8,-7,-6,-5,-4,-3,-2,-1,1,2,3,4,5,6,7,8,9.5,10,11,12], 
[-12,-11,-10,-9.5,-8,-7,-6,-5,-4,-3,-2,-1,1,2,3,4,5,6,7,8,9.5,10,11,12]], 
[(0, 1), (2, 0), (2, 3), (4, 2)])

Выходной формат: число строк, соответствующее количеству подстанций. В каждой строке два числа через пробел: номер узла-подстанции и максимальная абсолютная мощность. Порядок вывода подстанций может быть любой. Пример формата:

1 2.1
4 5.24
30 10.3

Решение заcчитывается, если вычисленная мощность подстанций различается с авторским решением не более, чем на 10^(-7).

Time Limit: 2 секунды

Memory Limit: 256 MB

Видео-разбор


Последнее изменение: Monday, 19 September 2022, 12:38