ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Ural SU contest. Petrozavodsk training camp. Winter 2008

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

I. Звезда смерти 2

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Давным-давно в далёкой-предалёкой галактике…
Боевая космическая станция «Звезда Смерти» была спроектирована ещё до начала Клонических войн. Через много лет она была передана в руки Империи для контроля над Внешними Территориями. «Звезда Смерти» имела более 100 миль в диаметре, была оснащена гравитонной пушкой, способной уничтожать целые планеты, а также могла нести на борту несколько тысяч истребителей. «Звезда Смерти» должна была наводить ужас на население и полностью исключить всякую возможность сопротивления властям Империи.
После того, как первая «Звезда Смерти» была уничтожена повстанцами, началось создание новой модели, ещё более смертоносной. Новая модель, как и первая, имеет форму шара и может поступательно перемещаться в N‑мерном пространстве. Она оснащена M жёстко закреплёнными криптоновыми двигателями. Если на i‑й двигатель подать X единиц энергии, то вклад этого двигателя в j‑ю координату вектора тяги составит Aij · X. В зависимости от режима работы, криптоновый двигатель может перемещать станцию вперёд либо назад (в этом случае X отрицательно). Итоговый вектор тяги равняется сумме вкладов каждого из M двигателей.
Перед началом движения станции специальный навигационный модуль определяет необходимые координаты вектора тяги (b1b2, …, bN). Ваша программа должна вычислить количество энергии, которое необходимо подать на каждый из двигателей так, чтобы длина вектора разности суммарной тяги и необходимой тяги была минимальна. В случае, если ответ неоднозначен, требуется дополнительно минимизировать сумму квадратов величин энергии, подаваемой на двигатели.

Исходные данные

В первой строке через пробел записаны числа N и M (1 ≤ NM ≤ 100). Далее в M строках по N чисел в строке следует матрица Aij. В последней строке записаны N чисел bj — координаты необходимого вектора тяги. Все числа Aij и bj целые и по модулю не превосходят 100.

Результат

Выведите M действительных чисел X1, …, XM с точностью в пять знаков после десятичной точки. Xi должно равняться количеству энергии, которое необходимо подать на i‑й двигатель. В случае, если ответов несколько, выведите любой.

Пример

исходные данныерезультат
4 3
2 3 -2 1
-1 2 1 3
4 2 3 -2
3 13 -9 13
4.00000 2.00000 -1.00000
Автор задачи: Алексей Самсонов
Источник задачи: Ural SU Contest. Petrozavodsk Winter Session, January 2008
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1668. Звезда смерти 2