A competition is being held between two teams: A and B. Team A has N players numbered from 1 to N. Team B has M players numbered from 1 to M.
The competition requires certain number of matches to be played. In each match, one person from each of the teams goes against one another, until one of them is defeated. The loser is then replaced by another player from his/her team. The team that fails to replace its player (means all players have already lost), loses the competition and no more matches are held.
To be more clear, the players in each team line up to play in their order. That means the first match will be always between the player number 1 in team A and the player number 1 in team B. After the first match, if the player number 1 in team A loses, then he/she will be replaced by the player number 2 in his team, i.e, the second match will be between player number 2 in team A and player number 1 in team B (in case team A has more than one player). Otherwise, the second match will be between player number 1 in team A and player number 2 in team B (in case team B has more than one player). And the two teams keep competing based on that rule until one team has all its players lost.
Given the probability of a player beating another, can you find the expected number of matches that will be played?
Input:
The first line of input file contains T, the number of test cases.
Each test case starts with two space-separated integers, N and M, denoting the number of players on team A and team B, respectively.
Each of the next N lines contains M decimal numbers, separated by a single space. The jth decimal number on ith line denotes the probability that the player number i of team A shall defeat the player number j of team B. All the decimal numbers only contain up to 2 digits after the decimal point.
Output:
Output exactly T numbers, each denoting the expected number of matches to be held in scenario of the corresponding test case. Print the answer upto 6 digits after decimal point. As, Hacker-Earth uses exact matching, you should ensure to print exactly 6 places.
Constraints:
1 ≤ T ≤ 3
1 ≤ N, M ≤ 1000
1 2 2 0.5 0.5 0.5 0.5
2.500000
Possibilities are as follows:
- 1A def 1B, 1A def 2B: Probability is 0.5 * 0.5 = 0.25 and number of matches is 2. - 1A def 1B, 2B def 1A, 2B def 2A: Probability is 0.5 * 0.5 * 0.5=0.125 and number of matches is 3 - 1A def 1B, 2B def 1A, 2A def 2B: Probability is 0.5 * 0.5 * 0.5=0.125 and number of matches is 3 - 1B def 1A, 1B def 2A: Probability is 0.5 * 0.5 = 0.25 and number of matches is 2. - 1B def 1A, 2A def 1B, 2A def 2B: Probability is 0.5 * 0.5 * 0.5=0.125 and number of matches is 3 - 1B def 1A, 2A def 1B, 2B def 2A: Probability is 0.5 * 0.5 * 0.5=0.125 and number of matches is 3
Thus final answer is:
0.25 * 2 + 0.125 * 3 + 0.125 * 3 + 0.25 * 2 + 0.125 * 3 + 0.125 * 3 = 2.5
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor