Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
King of Fighters
Time Limit: 3000MSMemory Limit: 131072K
Total Submissions: 1335Accepted: 251Special Judge


styc and Sempr are fond of the game King of Fighters (KOF). KOF is a two-player game where the two players each pick three different characters as their heroes each to fight several mano-a-mano rounds. The players can pick the same characters. Each round one hero of either player is eliminated. Once all three heroes of one player are eliminated, the other wins the game.

In the past versions, the set of characters to be picked as heroes is very limited. styc and Sempr have long been bored with them. Now they have just got the latest version of the game. In this version, up to M (M ≤ 105) characters are available. And a player can pick up to N (N ≤ 10) of them as his hero. To prevent the game from lasting too long since there’ll be more rounds to play, the rule is modified that the players’ heroes fight in pairs fixed before the game starts.. After some practice rounds, styc takes on Sempr in a bet that his heroes will beat all Sempr’s in a full N-round game. He has managed to know in advance the N characters Sempr will pick for the game and the probabilities that Sempr wins a round of all possible pairs of heroes. To win the bet, styc must be very careful at choosing his heroes, so that his winning probability is maximized.


The input contains several test cases. Each test case starts with a line containing the integer N and M. Then follow a probability matrix of N rows and M columns { pij }N × M, where pij is the probability that Sempr wins a round if his i-th hero fights with styc's choice of the j-th character as the hero. Process to end of file.


For each test case, output the probablity that styc wins the bet to arbitrary precision as long as the relative error does not exceed 10−6.

Sample Input

3 5
0.50 0.50 0.50 0.50 0.50
0.50 0.50 0.50 0.50 0.50
0.50 0.50 0.50 0.50 0.50

Sample Output



Outputting in scientific form is recommended.


[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator