Cowboys

Time limit2sMemory limit128 MB

Summary

Given N cowboys shooting in turns with hit probabilities and optimal target choice under strategic play, compute each cowboy's probability of being the sole survivor.

Level: Hard9 of 10
Topics: Game theory, Dynamic programming, Probability, Bit manipulation
Solved: No attempts yet

Problem

N cowboys take turns firing in cyclic order. The order is cowboy 1, cowboy 2, ..., cowboy N, then cowboy 1 again. A cowboy who has been shot is dead and no longer gets a turn. When only one cowboy remains alive, that cowboy is the winner.

Cowboy i hits the chosen target with probability Pi%. Each cowboy chooses a living opponent that maximizes their own probability of eventually surviving. If several targets give the same maximum probability, one of those targets is chosen uniformly at random. A missed shot still ends the shooter's turn and the next living cowboy takes a turn.

Every cowboy must aim at another living cowboy. Even if shooting into the air would seem better, they never do so. Compute the probability that each cowboy becomes the last survivor.

Input

The first line contains the number of cowboys N. (2 ≤ N ≤ 13)

The second line contains N integers P1, P2, ..., PN. Pi is the probability, in percent, that cowboy i hits the chosen target, and 1 ≤ Pi ≤ 100.

Output

Print N real numbers Q1, Q2, ..., QN on one line, separated by spaces. Qi is the probability, in percent, that cowboy i becomes the last survivor.

An absolute or relative error of at most 10^-2 is accepted.

Examples5

Example 1
Input
```
2
1 100
```
Expected output
```
1.00 99.00
```
Example 2
Input
```
3
100 99 98
```
Expected output
```
2.00 0.00 98.00
```
Example 3
Input
```
3
50 99 100
```
Expected output
```
25.38 74.37 0.25
```
Example 4
Input
```
3
50 99 99
```
Expected output
```
25.38 49.50 25.12
```
Example 5
Input
```
3
50 99 98
```
Expected output
```
25.63 24.63 49.74
```