Задание 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

Задание 9. Энергетические блоки

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

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

Узлы одного блока можно расположить в некотором порядке в одну цепочку. Если рядом находятся два узла с мощностями a и b, то соединение между ними даёт энергию a · b.

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

Определите сумму номеров строк таблицы, для которых выполнены оба условия:

• энергия блока делится на максимальное число строки без остатка;
• сумма трёх наибольших чисел строки больше суммы четырёх оставшихся чисел.

В ответе запишите только число.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза.

Например, если в куче было 10 камней, за один ход можно получить 11 или 20 камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 58. Победителем считается игрок, сделавший последний ход.

В начальный момент в куче было S камней, где 1 ≤ S ≤ 57.

Найдите минимальное значение S, при котором у Вани есть стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, но у Вани нет стратегии, позволяющей гарантированно выиграть своим первым ходом.

В ответе запишите одно целое число.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза.

Например, если в куче было 10 камней, за один ход можно получить 11 или 20 камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 58. Победителем считается игрок, сделавший последний ход.

В начальный момент в куче было S камней, где 1 ≤ S ≤ 57.

Найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть первым ходом, но может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

В ответе запишите найденные значения в порядке возрастания через пробел.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза.

Например, если в куче было 10 камней, за один ход можно получить 11 или 20 камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 58. Победителем считается игрок, сделавший последний ход.

В начальный момент в куче было S камней, где 1 ≤ S ≤ 57.

Укажите минимальное значение S, при котором Петя может выиграть своим первым ходом.

В ответе запишите одно целое число.

Текстовый файл содержит строку из символов A, B, C и D.

Определите количество непрерывных фрагментов строки, которые начинаются на букву A, заканчиваются на букву A и содержат ровно 30 букв C.

В ответе запишите одно целое число.

Для выполнения задания используйте файл: 24_A_30_C_01.txt

Текстовый файл содержит строку из символов A, B, C, D и E.

Определите максимальную длину непрерывного фрагмента строки, в котором буква A встречается не более 50 раз.

В ответе запишите одно целое число.

Для выполнения задания используйте файл: 24_50_A_01.txt