CT16E  Fish
n fish, numbered from 1 to n, live in a lake. Every day right one pair of fish meet, and the probability of each other pair meeting is the same. If two fish with indexes i and j meet, the first will eat up the second with the probability a_{ij}, and the second will eat up the first with the probability a_{ji} = 1  a_{ij}. The described process goes on until there are at least two fish in the lake. For each fish find out the probability that it will survive to be the last in the lake.
Input
The first line contains integer n (1 ≤ n ≤ 18) — the amount of fish in the lake. Then there follow n lines with n real numbers each — matrix a. a_{ij} (0 ≤ a_{ij} ≤ 1) — the probability that fish with index i eats up fish with index j. It's guaranteed that the main diagonal contains zeros only, and for other elements the following is true: a_{ij} = 1  a_{ji}. All real numbers are given with not more than 6 characters after the decimal point.
Output
Output n spaceseparated real numbers accurate to not less than 6 decimal places. Number with index i should be equal to the probability that fish with index i will survive to be the last in the lake.
Example
Input:5
0 1 1 1 1
0 0 0.5 0.5 0.5
0 0.5 0 0.5 0.5
0 0.5 0.5 0 0.5
0 0.5 0.5 0.5 0
Output:
1.000000 0.000000 0.000000 0.000000 0.000000
hide comments
iampk:
20181204 17:30:40
Can someone please provide a good test case for the problem? 

magick968:
20110924 11:52:26
Time limit is far too strict. 

Mahesh Chandra Sharma:
20101208 22:55:26
For the max case of n = 18 my program runs on local machine in just 1.1 sec. still it is giving TLE.


little zaza:
20100717 02:40:08
TL is a too strict, memoization got TLE 

Phan Công Minh:
20100712 04:39:28
n^2* 2^n is enough to pass . if You got tle, you should inprove your code. 

Ravi Kiran:
20100711 14:22:30
O(N*N*2^N) is enough to get ac.Maybe evident optimisations are required!


Ishan:
20100708 07:45:00
O(n*n*2^n) is getting tle.time limit should be relaxed. 

[Rampage] Blue.Mary:
20100626 10:24:17
Maybe 5 second time limit is more proper? 

kostya:
20100625 05:12:03
0.9047615 in result must be 0.904761 or 0.904762? 

Phan Công Minh:
20100625 01:10:50
2

Added by:  Phan Công Minh 
Date:  20100622 
Time limit:  0.288s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 SQLITE VB.NET 
Resource:  Codeforces 