Cod sursa(job #1470967)

Utilizator dnprxDan Pracsiu dnprx Data 12 august 2015 18:56:39
Problema Dezastru Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <bits/stdc++.h>

using namespace std;

int n, st[30], k;
double a[50], solutie;
double best[30][30];

void Citire()
{
    int i;
    ifstream fin("dezastru.in");
    fin >> n >> k;
    for (i = 1; i <= n; ++i)
        fin >> a[i];
    fin.close();
}

int Comb( int n, int k )
{
    if (n == k || k == 0) return 1;
    if (n - k == 1 || k == 1) return n;
    return Comb( n - 1, k - 1 ) + Comb( n - 1, k );
}

void Dinamica()
{
    int i, j;
    /// best[i,j]=numarul de posibilitati de a alege
    /// din a[1..i] exact j valori

    /// initializare
    for (i = 0; i <= n; i++)
        best[i][0] = 1;

    /// best[i,j] = best[i-1,j] daca nu aleg pe a[i]
    ///           + best[i-1,j-1] daca aleg pe a[i]
    for (i = 1; i <= n; i++)
        for (j = 1; j <= k; j++)
            best[i][j] = best[i-1][j] + best[i-1][j-1]*a[i];
}

void Afisare()
{
    ofstream fout("dezastru.out");
    solutie = best[n][k] / Comb(n, k);
    fout << fixed << setprecision(6) << solutie << "\n";
    fout.close();
}

int main()
{
    Citire();
    Dinamica();
    Afisare();
    return 0;
}