16655번 - Halves Not Equal 스페셜 저지다국어

The king died and his gold had to be divided among his n wives. He had not left his will about the parts of his wives, so they started arguing. The i-th wife claimed that she should get ai dinars. However, it turned out that the total property of the king was only s dinars, and s ≤ a₁ + a₂ + . . . + a_n. A wise man was called to help divide the king’s inheritance. But he said that he only knew a fair way to divide gold between two persons.

The fair way is the following. Without loss of generality, let the claims of the two persons be a₁ ≤ a₂, and let there be b dinars of gold to be divided, 0 ≤ b ≤ a₁ + a₂. If b ≤ a₁, each of the persons would get b/2 dinars. If a₁ < b < a₂, the first one would get a₁/2 dinars and the second one would get b − a₁/2 dinars. Finally, if a₂ ≤ b, the first one would get a₁/2+ (b−a₂)/2 and the second one would get a₂/2+ (b−a₁)/2. Gold can be divided to any fractional part, so the amount one gets can be fractional. Note that the amount each one would get is a monotonic and continuous function of b.

Now you have been called as an even wiser person to help divide the gold among the n wives. Each wife should get no more than she claims. The division is called fair if for any two wives who claim a_i and a_j dinars of the inheritance and get c_i and c_j dinars, correspondingly, these values are the fair way to divide c_i + c_j dinars between them.

Help the wives of the late king divide his inheritance.

The first line of the input contains n — the number of wives of the king (2 ≤ n ≤ 5000).

The second line contains n integers a₁, a₂, . . . , a_n (1 ≤ a_i ≤ 5000).

The third line contains an integer s (0 ≤ s ≤ a₁ + a₂ + . . . + a_n).

Output n floating point numbers c₁, c₂, . . . , c_n — the amounts of gold each wife should get in a fair division. For each pair of wives i and j the absolute or relative difference between their parts and their parts in the fair way to divide ci + cj between them must not exceed 10⁻⁹. The sum of ci must be equal to s with an absolute or relative error of at most 10⁻⁹.

It can be proved that a fair division always exists. If there is more than one solution, output any of them.