ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1668. Death Star 2

Time limit: 0.5 second
Memory limit: 64 MB
A long time ago in a galaxy far, far away…
The battle space station “Death star” was designed even before the Clone wars. Many years later, it was given to the Empire to control the Outer Rim Territories. The “Death star” was about 100 miles in diameter, was equipped with a graviton gun, capable of destroying whole planets, and could carry a few thousands of space fighters on board. The “Death star” was supposed to terrify the population and to absolutely exclude any possibility of resisting the power of the Empire.
After the first “Death star” had been destroyed by the rebels, the construction of a new, even more deadly model started. The new model, as the first one, has a ball shape and can translationally move in N‑dimensional space. It is equipped with M firmly anchored krypton engines. If the i‑th engine is provided with X units of energy, its contribution to the j‑th coordinate of the jet thrust vector will be equal to Aij · X. Note that the engines are bidirectional, so supplying a negative X just means using it to thrust in the opposite direction with |X| units of energy. The resulting jet thrust vector is equal to the sum of contributions of each of M engines.
Before the beginning of the movement a special navigational module calculates the required coordinates of the jet thrust vector (b1b2, …, bN).Your program should calculate how much units of energy should be provided to each of the engines in such a way, that the length of the vector of difference between the resulting jet thrust and the required jet thrust will be minimal. If the answer is ambiguous, the sum of squares of the quantity of energy, provided to the engines, should also be minimized.


The first line contains two integers N and M separated with a space (1 ≤ NM ≤ 100). The following M lines with N numbers in each line represent the matrix Aij. The last line contains N numbers bj — the coordinates of required jet thrust vector. All Aij and bj are integers with absolute values not exceeding 100.


Output M real numbers X1, …, XM precise up to 5 digits after the decimal point. Xi should be equal to the quantity of energy, provided to i‑th engine. If there is more than one answer, you can output any one.


4 3
2 3 -2 1
-1 2 1 3
4 2 3 -2
3 13 -9 13
4.00000 2.00000 -1.00000
Problem Author: Alex Samsonov
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, January 2008