# CFR 442 B. Andrey and Problem ( Math, Probability, Greedy )

Problem - B - Codeforces

The first line contains a single integer n (1 ≤ n ≤ 100) — the number of Andrey's friends. The second line contains n real numbers pi (0.0 ≤ pi ≤ 1.0) — the probability that the i-th friend can come up with a problem. The probabilities are given with at most 6 digits after decimal point.

Sigma{ P[ i ] * Pi{ 1 - P[ j ], for all i != j }, for all 0 ≤ i < n }
= Sigma{ P[ i ] / ( 1 - P[ i ] ), for all 0 ≤ i < n } * Pi{ 1 - P[ i ], for all 0 ≤ i < n }

S = Sigma{ P[ i ] / ( 1 - P[ i ] ), for all 0 ≤ i < n }
F = Pi{ 1 - P[ i ], for all 0 ≤ i < n }
delta( x ) = ( S + P[ x ] / ( 1 - P[ x ] ) * ( F * ( 1 - P[ x ] ) ) - S * F
= F * P[ x ] * ( 1 - S )

Assuming delta( x ) - delta( y ) > 0 :
delta( x ) - delta( y ) = F * ( 1 - S ) * ( P[ x ] - P[ y ] ) > 0, which implies P[ x ] > P[ y ]

O( N )

```#include <bits/stdc++.h>
using namespace std;

int N;
double P[ 100 ];

signed main(){
ios::sync_with_stdio( 0 );
cin >> N;
for( int i = 0; i < N; ++i ){
cin >> P[ i ];
if( P[ i ] == 1.0 ){ // otherwise RE later for division with 0
cout << 1.0 << endl;
exit( 0 );
}
}
double ans = 0.0;
sort( P, P + N, greater< double >() );
for( int i = 0; i < N; ++i ){
static double sum = 0.0, pi = 1.0;
sum += P[ i ] / ( 1.0 - P[ i ] );
pi *= 1.0 - P[ i ];
ans = max( ans, sum * pi );
}
cout << fixed << setprecision( 10 ) << ans << endl;
return 0;
}
```