Cod sursa(job #2307545)

Utilizator driver71528@gmail.comTerec Andrei-Sorin [email protected] Data 24 decembrie 2018 19:56:22
Problema Dezastru Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <iostream>
#include <fstream>

using namespace std;

int rez[26];
double attack[26];
int n,k;
ofstream g("dezastru.out");
double probability;
void backtracking(int st)
{
    if(st==k+1)
    {
        double pr=1;
        for(int i=1;i<=k;i++)
            pr*=attack[rez[i]];
        probability+=pr;
    }
    else
    {
        int nr=n-rez[k]+1;
        while(rez[k]<=n)
        {
            backtracking(st+1);
            for(int i=st;i<=k;i++)
                rez[i]++;
        }
        for(int i=st;i<=k;i++)
            rez[i]-=nr;
    }

}

long long combinari(int n,int k)
{
    k=k>n-k? k : n-k;
    int x,y;
    x=y=1;
    for(int i=k+1;i<=n;i++)
        x*=i;
    for(int i=2;i<=n-k;i++)
        y*=i;
    return x/y;
}

int main()
{
    g.precision(6);
    ifstream f("dezastru.in");
    f>>n>>k;
    for(int i=1;i<=k;i++)
        rez[i]=i;
    for(int i=1;i<=n;i++)
        f>>attack[i];
    backtracking(1);
    g<<probability/combinari(n,k);
    g.close();
    return 0;
}