0061. Загрузка оборудования

Имя входного файла:	equip.in
Имя выходного файла:	equip.out
Ограничение по времени:	2 s
Ограничение по памяти:	64 megabytes

Вася проходит производственную практику в вычислительной лаборатории университета, где обслуживает сложнейшую мультипроцессорную систему, параллельно решающую m задач для нужд университета и m – для нужд организаций-подрядчиков. Работы выполняет суперкомпьютер, m*m процессоров которого составляют матрицу из m строк и m столбцов. Процессоры специализированы, поэтому их производительность неодинакова. Она выражается целым числом a_ij миллионов операций в секунду, выполняемых процессором (i,j).

Для решения каждой из <<внутриуниверситетских>> задач с номером i∈1..m требуются все процессоры с номерами (i,j) j∈1..m, причем все они в равной степени загружены этой задачей (т. е. на каждом из этих процессоров этой задачей выполняется одинаковое число операций в секунду), для решения внешней задачи j∈1..m задействуются процессоры (i,j) i∈1..m тем же образом.

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

Формат входного файла

Первая строка исходного файла содержит число 1≤ m≤ 100 – размерность матрицы суперкомпьютера, последующие m строк – производительности процессоров.

Формат выходного файла

Первая строка вывода содержит искомую суммарную загрузку системы задачами. Вторая строка содержит m чисел, разделенных пробелами – i-ое число есть число миллионов операций, выполняемых i-ой университетской задачей на каждом из процессоров (i,j) (напомним, что для различных j эти числа совпадают). Третяя строка содержит аналогичную информацию о задачах организаций-подрядчиков. Все числа следует выводить с 6 знаками после запятой.

Пример:

equip.in	equip.out
3 4 5 6 5 7 9 6 9 12	19.000000 3.000000 5.000000 6.000000 0.000000 2.000000 3.000000

Источник: Petrozavodsk Winter 2003. Take-Off, Monday, February 03

Обсудить       Отправить решение



Версия для печати