Colorful World 的算法 5C

Recently little F buys 2n lights and aligns them in a circle at his beautiful garden. On the first day, when night falls, little F lights up the lights with 2n different colors, and his girlfriend is lost in the dreamy scene.

On the next 2n-1 days, little F turns the colors of lights counter-clockwise once every day in order to please his girlfriend with different scene. Let’s say on the first day little F lights up the i-th (starts from 1) light with color ci, then on the second day, the i-th light’s color becomes ci+1 and (2n)-th light’s color becomes c1. On the other side, every light has certain brightness, i.e., no matter what color the light is, its brightness will never change.

On the k-th (starts from 1) day his girlfriend can get hk happiness. On the (2n+1)-th day, the scene is as same as the one on the first day and h2n+1 is equal to h1. Little F stops the lights show and quickly realizes that his girlfriend has various preferences over different colors. For color cj, if her likeness is aj, then it will give (aj∙bi) happiness if the brightness of the i-th light, with color cj, is bi. Finally hk equals to the sum of happiness of all the lights on the k-th day.

Little F has already recorded bj for each color cj and hk on each day. He wants to calculate ai, thus he can find better ways to please his girlfriend in the future. It’s guaranteed that for the given input, there is only one solution to ai.

The first line contains an integer T (1 ≤ T ≤ 20) -- the number of test cases.

For each test case:
The first line contains an integer n. 1 ≤ n ≤ 10.
The second line contains 2n integers, indicate b1, b2, ... , b2n. 0 ≤ b ≤ 5 000.
The third line contains 2n integers, indicate h1, h2, ... , h2n. 0 ≤ h ≤ 5 000.
For each test case, you should output 2n real integer a1, a2, ... , a2n in order, separated by a single space in a single line. Each number should be rounded to 2 digits after the decimal point.
8 10
4 9
1.61 -0.89

Csdn user default icon