Cod sursa(job #1017247)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 27 octombrie 2013 16:16:22
Problema Dezastru Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <iomanip>

using namespace std;

int N, M;
int st[30];
double v[30];
long long fact[30];
double sum;
long long inmul;

void gen()
{
    fact[1] = 1;

    for ( int i = 2; i <= 30; ++i )
            fact[i] = fact[i - 1] * i;
}

void afis()
{
    double prod = 1;

    for ( int i = 1; i <= M; ++i )
            prod *= v[ st[i] ];

    prod *= fact[M];

    sum += prod;
    inmul++;
}

void bkt( int k )
{
    if ( k > M )
            afis();
    else
        for ( int i = st[k - 1] + 1; i <= N - M +k; ++i)
        {
            st[k] = i;
            bkt( k + 1 );
        }
}

int main()
{
    ifstream f("dezastru.in");
    ofstream g("dezastru.out");

    f >> N >> M;

    for ( int i = 1; i <= N; ++i )
            f >> v[i];

    gen();
    bkt( 1 );
    inmul *= fact[M];

    g << fixed << setprecision( 10 );
    g << sum / inmul;

    return 0;
}