442B

Description

Give the probabilities of each one in $n$ friends to come up with exactly one problem. We should invite a group of friends so that the probability for them to up exactly one problem in total is maximized.

Tutorial

The math deduction process is very complex. The easiest way to find the solution to this problem is to use brute force for to discover the patterns in the answer, if you cannot discover the pattern by hand. The pattern is as follows. We should sort the friends by their probabilites from the lowest to the highest. The group we choose is always the suffix of this probability array.

By the way, the formula for the probability for a group to come up with exactly one problem is $P=(\prod\limits_{i=1}^{n}(1-p_i))\times(\sum\limits_{i=1}^{n}\frac{p_i}{1-p_i})$.

Solution

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 105;

int n;
double f[MAX_N];

void input()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%lf", &f[i]);
    }
}

void work()
{
    double ans = 0;
    double sum = 0;
    double product = 1;
    for (int i = 0; i < n; i++)
    {
        sum *= 1 - f[i];
        sum += product * f[i];
        product *= 1 - f[i];
        if (sum > ans)
        {
            ans = sum;
        }
    }
    printf("%.12f\n", ans);
}

int main()
{
    input();
    sort(f, f + n);
    reverse(f, f + n);
    work();
    return 0;
}