Cod sursa(job #1467492)

Utilizator tudor00Stoiean Tudor tudor00 Data 3 august 2015 15:06:52
Problema Dezastru Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
///vaianta 1 cu backtracking
/*#include <fstream>
#include <iomanip>

using namespace std;

ifstream in("dezastru.in");
ofstream out("dezastru.out");

int n,k;
int v[20];
float v2[30];
long double suma=0;
long double cnk=0;

int verificare(int nivel)
{
    bool ok=0;
    for(int i=1; i<nivel; i++)
    {
        if(v[i]!=v[nivel]) ok=0;
        else
        {
            ok=1;
            break;
        }
    }
    if(ok==0) return 0;
    return 1;

}

void afisare()
{
    long double q=1;
    for(int i=1; i<=k; i++) q=q*v2[v[i]];
    cnk++;
    suma+=q;
    ///out<<q<<" ";
}

void btk (int nivel)
{
    for(int i=1; i<=n; i++)
    {
        v[nivel]=i;
        if(verificare(nivel)==0)
        {
            if((nivel+1)>n)
            {
                afisare();
            }
            else
            {
                btk(nivel+1);
            }
        }
    }
}

int main()
{
    in>>n>>k;
    for(int j=1;j<=n;j++) in>>v2[j];
    btk(1);

    ///cnk=combinari de n luate cate k

    suma=suma/cnk;
    out<<fixed<<setprecision(6)<<suma;

    in.close();
    out.close();
    return 0;
}
*/
#include <fstream>
#include <iomanip>

using namespace std;

ifstream in("dezastru.in");
ofstream out("dezastru.out");

long double a[30][30];
long double v[30];
unsigned long  n,k,cnk=1;

int main()
{
    in>>n>>k;
    for(int i=1;i<=n;i++) in>>v[i];

    for(int i=0;i<=n;i++) a[i][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=k;j++)
    {
        a[i][j]=a[i-1][j]+a[i-1][j-1]*v[i];
    }
    for(int i=1;i<=n;i++) cnk=cnk*i;
    for(int i=1;i<=n-k;i++) cnk=cnk/i;
    for(int i=1;i<=k;i++) cnk=cnk/i;

    out<<fixed<<setprecision(6)<<a[n][k]/cnk;

    in.close();
    out.close();
    return 0;
}