Cod sursa(job #841913)

Utilizator enedumitruene dumitru enedumitru Data 25 decembrie 2012 15:18:50
Problema Dezastru Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
/*  Problema se poate rezolva si folosind programarea dinamica.
    Se construieste matricea A unde A[i][j] = suma tuturor produselor de j factori alesi din primele i numere.
    Recurenta se poate calcula usor A[i][j]=A[i-1][j]+A[i-1][j-1]*P[i].
    Probabilitatea ceruta va fi A[n][k] impartita la C[n][k] (cinari de n luate cate k). Complexitate O(n*k).
*/
#include<fstream>
//#include<iomanip>
using namespace std;
int n, k, i, j;
double a[26][26],p[26], c=1;
ifstream f("dezastru.in");
ofstream g("dezastru.out");
int main()
{   f>>n>>k; a[0][0]=1.0;
    for(i=1; i<=n; ++i) f>>p[i], a[i][0]=1.0;
    for(i=1; i<=n; ++i)
        for(j=1; j<=k; ++j)
            a[i][j]=a[i-1][j]+a[i-1][j-1]*p[i];
    for(i=k+1; i<=n; ++i) c*=i;
    for(i=2; i<=n-k; ++i) c/=i;
    g.precision(7); g<<a[n][k]/c;
    return 0;
}