Задание 26. Энергетические комплекты2

Задание выполняется с использованием прилагаемого файла.

На складе исследовательской станции хранятся комплекты энергетических узлов. Каждый комплект состоит из двух узлов. Для каждого узла известна его мощность — натуральное число.

Перед сборкой каждый комплект проходит проверку.

Пусть R — разность мощностей двух узлов комплекта.

• Если R < D, то комплект считается сбалансированным, и оба его узла отправляются на основную линию сборки.
• Если D ≤ R ≤ 2D, то комплект считается разделяемым: более мощный узел отправляется на основную линию сборки, а менее мощный — в резерв.
• Если R > 2D, то комплект считается нестабильным, и оба его узла отправляются в резерв.

Из узлов основной линии и из узлов резерва отдельно собирают энергетические блоки. Каждый энергетический блок состоит ровно из четырёх узлов.

Если мощности узлов блока равны x, y, z и t, где x ≤ y ≤ z ≤ t, то блок считается стабильным, если выполнены все условия:

• y − x ≥ K;
• z − y ≥ K;
• t − z ≥ K.

Энергия такого энергетического блока равна сумме произведений мощностей соседних узлов:

x·y + y·z + z·t

Каждый узел можно использовать не более чем в одном энергетическом блоке одной линии. Основная линия и резерв рассматриваются независимо.

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

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

Определите:

1. максимальное количество стабильных энергетических блоков, которое можно собрать из узлов основной линии;
2. модуль разности между максимальной возможной энергией одного стабильного энергетического блока основной линии и максимальной возможной энергией одного стабильного энергетического блока резерва.

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

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

В первой строке входного файла находятся три натуральных числа:

N K D

где:

• N — количество комплектов энергетических узлов;
• K — минимальная допустимая разница мощностей соседних узлов в стабильном энергетическом блоке;
• D — порог разности мощностей узлов одного комплекта.

В следующих N строках записаны по два натуральных числа — мощности двух узлов одного комплекта.

Задание 26. Энергетические комплекты

Задание выполняется с использованием прилагаемого файла.

На складе исследовательской станции хранятся комплекты энергетических узлов. Каждый комплект состоит из двух узлов. Для каждого узла известна его мощность — натуральное число.

Перед сборкой каждый комплект проходит проверку.

Пусть R — разность мощностей двух узлов комплекта.

• Если R < D, то комплект считается сбалансированным, и оба его узла отправляются на основную линию сборки.
• Если D ≤ R ≤ 2D, то комплект считается разделяемым: более мощный узел отправляется на основную линию сборки, а менее мощный — в резерв.
• Если R > 2D, то комплект считается нестабильным, и оба его узла отправляются в резерв.

Из узлов основной линии и из узлов резерва отдельно собирают стабильные энергоблоки. Каждый энергоблок состоит ровно из трёх узлов.

Если мощности узлов блока равны x, y и z, где x ≤ y ≤ z, то блок считается стабильным, если выполнены оба условия:

• y − x ≥ K;
• z − y ≥ K.

Энергия такого энергоблока равна:

x·y + y·z

Для основной линии и для резерва отдельно требуется собрать максимально возможное количество стабильных энергоблоков.

Если существует несколько способов собрать максимально возможное количество стабильных энергоблоков, выбирается такой способ, при котором суммарная энергия собранных энергоблоков максимальна.

Определите:

1. максимальное количество стабильных энергоблоков, которое можно собрать из узлов основной линии;
2. модуль разности между максимальной суммарной энергией стабильных энергоблоков основной линии и максимальной суммарной энергией стабильных энергоблоков резерва.

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

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

В первой строке входного файла находятся три натуральных числа:

N K D

где:

• N — количество комплектов энергетических узлов;
• K — минимальная допустимая разница мощностей соседних узлов в стабильном энергоблоке;
• D — порог разности мощностей узлов одного комплекта.

В следующих N строках записаны по два натуральных числа — мощности двух узлов одного комплекта.

Пример входного файла

10 5 4
10 13
20 27
30 36
40 43
50 60
22 24
70 82
15 25
33 34
45 52

После проверки комплектов на основную линию попадут узлы:

10 13 24 22 43 40 34 33 27 36 52

В резерв попадут узлы:

20 30 50 60 70 82 15 25 45

Для основной линии можно собрать 3 стабильных энергоблока с максимальной суммарной энергией:

24 34 40
33 43 52
10 22 27

Их суммарная энергия равна:

24·34 + 34·40 + 33·43 + 43·52 + 10·22 + 22·27 = 6631

Для резерва можно собрать 2 стабильных энергоблока с максимальной суммарной энергией:

50 60 82
15 25 30

Их суммарная энергия равна:

50·60 + 60·82 + 15·25 + 25·30 = 9045

Модуль разности:

9045 − 6631 = 2414

Ответ для примера:

3 2414