Условие задачи
Задание 9. Энергетические блоки
Задание выполняется с использованием прилагаемого файла.
Откройте файл электронной таблицы, содержащей в каждой строке семь натуральных чисел. Каждая строка описывает энергетический блок, состоящий из семи узлов. Числа в строке обозначают мощности этих узлов.
Узлы одного блока можно расположить в некотором порядке в одну цепочку. Если рядом находятся два узла с мощностями a и b, то соединение между ними даёт энергию a · b.
Энергией блока будем считать наибольшую возможную сумму произведений соседних узлов, которую можно получить при некотором расположении всех семи узлов.
Определите сумму номеров строк таблицы, для которых выполнены оба условия:
- энергия блока делится на максимальное число строки без остатка;
- сумма трёх наибольших чисел строки больше суммы четырёх оставшихся чисел.
В ответе запишите только число.
Подсказка
Подсказка
В каждой строке семь чисел. Их можно переставлять в любом порядке, поэтому энергия строки не обязана считаться в том порядке, в котором числа записаны в таблице.
Чтобы получить наибольшую энергию блока, подумайте, какие числа выгоднее поставить рядом. Большие числа дают большие произведения, поэтому обычно их выгодно располагать ближе друг к другу.
Например, пусть в строке было бы не семь, а пять чисел:
10 20 30 40 50
Если расположить их просто по возрастанию, получится цепочка:
10 20 30 40 50
Её энергия равна:
10·20 + 20·30 + 30·40 + 40·50 = 4000
Но можно расположить числа иначе:
10 30 50 40 20
Тогда энергия будет больше:
10·30 + 30·50 + 50·40 + 40·20 = 4600
Значит, для каждой строки нужно искать именно максимальную возможную энергию, а не просто считать произведения соседних чисел в исходном порядке.
Один из удобных способов рассуждения — сначала отсортировать числа строки, а затем попробовать расположить их так, чтобы самые большие числа участвовали в произведениях с другими большими числами.
После того как максимальная энергия строки найдена, останется проверить два условия:
- делится ли найденная энергия на максимальное число строки;
- больше ли сумма трёх наибольших чисел суммы четырёх остальных.