2489. Test Passing Probability

单点时限: 2.0 sec

内存限制: 256 MB

Dave is taking a multiple choice test on the Internet. Dave possibly gets many opportunities to submit his answers to the test, but he passes only if he gets all the questions correct. He must answer every question on the test to make a submission. The only information he receives after he submits is whether he has passed.

For each question, he estimates the probability that each of 4 responses is correct, independent of his responses to other questions. Given a fixed number of submissions he can make, Dave wants to choose his responses so that he maximizes the probability of passing the test.

What is the probability that Dave will pass the test if he chooses his responses optimally?

输入格式

The first line of input gives the number of cases, C(1 ≤ C ≤ 100 ). C test cases follow.

Each test case starts with a line containing M(1 ≤ M ≤ 10000 ) and Q(1 ≤ Q ≤ 30 ). Dave is allowed to make M submissions to solve the test. There are Q questions on the test. Q lines follow, each containing 4 probabilities of correctness. There will be at most 6 digits after the decimal point. The probabilities for each line are non-negative and sum to 1.

输出格式

For each test case, output one line containing “Case #X: Y” where X is the number of the test case (starting from 1), and Y is the probability of success.

Answers with a relative or absolute error of at most 10−6 will be considered correct.

样例

Input
3
10 2
0.25 0.25 0.25 0.25
0.25 0.25 0.25 0.25
64 3
0.3 0.4 0.0 0.3
1.0 0.0 0.0 0.0
0.2 0.2 0.2 0.4
3 2
0.5 0.17 0.17 0.16
0.5 0.25 0.25 0.0
Output
Case #1: 0.625
Case #2: 1.0
Case #3: 0.5

0 人解决,1 人已尝试。

0 份提交通过,共有 2 份提交。

9.9 EMB 奖励。

创建: 15 年,3 月前.

修改: 6 年,10 月前.

最后提交: 3 年,7 月前.

来源: GCJ 2008

题目标签