Cod sursa(job #2588942)

Utilizator VanillaSoltan Marian Vanilla Data 25 martie 2020 16:34:44
Problema Dezastru Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream in ("dezastru.in");
ofstream out ("dezastru.out");
int n, k;
vector <double> pr (26);
int rz [26];
bool used[26];
double rs = 0;

void subsets()
{
    for (int i = 0; i < (1 << n); i++){
        int count = 0;
        double temp = 1;
        for (int j = 0; j < n; j++){
            if ((i & (1 << j)) != 0){
                temp *= pr[j+1];
               //cout << j+1 << " ";
                count++;
            }
        }
        if (count == k){
            rs+= temp;
            //cout << rs << "\n";
            //cout  << "\n" << temp << "\n";
            //cout << "\n";
        }
    }
}

void backtrack(int step)
{
    if (step == n+1){
        double temp = pr[rz[1]];
        for (int i = 2; i <= k; i++){
            temp*=pr[rz[i]];
        }
        rs+=temp;
        //cout << "\n";
        return;
    }
    for (int i = 1; i <=n ;i++){
        if (!used[i]){
            used[i] = 1;
            rz[step] = i;
            backtrack(step+1);
            used[i] = 0;
        }
    }
}

int main()
{
    in >> n >> k;
    for (int i = 1; i <= n; i++){
        in >> pr[i];
    }
    double fact1 = 1;
    double fact2 = 1;
    subsets();

    if (k > n-k){
        for (int i = k+1; i <=n; i++)
            fact1 *=i;
        for (int i = 2; i <= n-k; i++)
            fact2 *= i;
    }
    else{
        for (int i = n-k+1; i <=n; i++){
            fact1 *=i;
        }
        for (int i = 2; i <= k; i++){
            fact2 *=i;
        }
    }
    double fact3 = fact1 * fact2;
    out << rs / fact3;
    return 0;
}