<h1 id="heading">题目</h1>
<p>{% fold 点击显/隐题目 %}</p>
<div class="oj"><div class="part" title="Description">
Organizing a programming contest is not an easy job. To avoid making the problems too difficult, the organizer usually expect the contest result satisfy the following two terms: 
1. All of the teams solve at least one problem. 
2. The champion (One of those teams that solve the most problems) solves at least a certain number of problems. 
<p>Now the organizer has studied out the contest problems, and through the result of preliminary contest, the organizer can estimate the probability that a certain team can successfully solve a certain problem.</p>
<p>Given the number of contest problems M, the number of teams T, and the number of problems N that the organizer expect the champion solve at least. We also assume that team i solves problem j with the probability Pij (1 &lt;= i &lt;= T, 1&lt;= j &lt;= M). Well, can you calculate the probability that all of the teams solve at least one problem, and at the same time the champion team solves at least N problems?</p>
</div><div class="part" title="Input">
The input consists of several test cases. The first line of each test case contains three integers M (0 &lt; M &lt;= 30), T (1 &lt; T &lt;= 1000) and N (0 &lt; N &lt;= M). Each of the following T lines contains M floating-point numbers in the range of [0,1]. In these T lines, the j-th number in the i-th line is just Pij. A test case of M = T = N = 0 indicates the end of input, and should not be processed.
</div><div class="part" title="Output">
For each test case, please output the answer in a separate line. The result should be rounded to three digits after the decimal point.
</div><div class="samp"><div class="clear"></div><div class="input part" title="Sample Input">
2 2 2
0.9 0.9
1 0.9
0 0 0
</div><div class="output part" title="Sample Output">
0.972
</div><div class="clear"></div></div></div>
{% endfold %}

<h1 id="heading-1">题解</h1>
<p><code>dp[i][j][k]</code> 表示第i个队伍在前j道题中做出k题</p>
<p>有递推式<br>
<code>dp[i][j][k] += dp[i][j - 1][k - 1] * Prob[i][j] + dp[i][j - 1][k] * (1 - Prob[i][j])</code></p>
<p>计算出来后,需要用概率的知识计算满足<strong>每一队都至少过一题,并且至少有一队过N题</strong>的概率</p>
<p>首先计算出所有队伍至少过一题的数量</p>
<h1 id="heading-2">代码</h1>
<p>{% fold 点击显/隐代码 %}```cpp Check the difficulty of problems <a href="https://github.com/OhYee/sourcecode/tree/master/ACM">https://github.com/OhYee/sourcecode/tree/master/ACM</a> 代码备份<br>
#include <cstdio><br>
#include <iomanip><br>
#include <iostream><br>
using namespace std;</p>
<p>const int maxT = 1005;<br>
const int maxM = 35;</p>
<p>double Prob[maxT][maxM];<br>
double dp[maxT][maxM][maxM];</p>
<p>int main() {<br>
int M, T, N;<br>
while (scanf(&quot;%d%d%d&quot;, &amp;M, &amp;T, &amp;N) != EOF) {<br>
if (!(M | T | N))<br>
break;</p>
<pre><code>    for (int i = 1; i &lt;= T; ++i)
        for (int j = 1; j &lt;= M; ++j)
            scanf(&quot;%lf&quot;, &amp;Prob[i][j]);

    for (int i = 1; i &lt;= T; ++i)
        dp[i][0][0] = 1.0;

    // dp[i][j][k] 第i个队伍在前j道题中做出k题
    for (int i = 1; i &lt;= T; ++i)
        for (int j = 1; j &lt;= M; ++j)
            for (int k = 0; k &lt;= j; ++k) {
                dp[i][j][k] = 0.0;
                if (k != 0)
                    dp[i][j][k] += dp[i][j - 1][k - 1] * Prob[i][j];
                // if (k != j)
                dp[i][j][k] += dp[i][j - 1][k] * (1 - Prob[i][j]);
            }

    double P1 = 1.0; //有队伍达到N题
    double P2 = 1.0; //有队伍未达到1题
    for (int i = 1; i &lt;= T; ++i) {
        double sum = 0.0;
        for (int j = 1; j &lt; N; ++j)
            sum += dp[i][M][j];
        P1 *= sum;
        P2 *= 1 - dp[i][M][0];
    }
    // P1 = 1 - P1;
    // P2 = 1 - P2;

    // printf(&quot;%.3f\n&quot;, P1 - P2);
    cout &lt;&lt; fixed &lt;&lt; setprecision(3) &lt;&lt; P2 - P1 &lt;&lt; endl;
}
return 0;
</code></pre>
<p>}</p>
<pre style="background-color:#fff">{% endfold %}</pre>

POJ 2151.Check the difficulty of problems