Cod sursa(job #2228651)

Utilizator andreisontea01Andrei Sontea andreisontea01 Data 4 august 2018 15:30:45
Problema Dezastru Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <iostream>
#include <fstream>
#include <iomanip>

using namespace std;

double prob[30];
int perm[30];
bool block[30];

double ans;
int n, k, cnt;

void backtrack(int pos){
    if(pos == n + 1){
        cnt++;
        double totprob = 1.0000000;
        for(int i = 1; i <= k; ++i)
            totprob *= prob[perm[i]];
        ans += totprob;
    }
    for(int i = 1; i <= n; ++i){
        if(!block[i]){
            perm[pos] = i;
            block[i] = 1;
            backtrack(pos + 1);
            perm[pos] = 0;
            block[i] = 0;
        }
    }
    return;
}

int main()
{
    ifstream fin("dezastru.in");
    ofstream fout("dezastru.out");
    fin >> n >> k;
    for(int i = 1; i <= n; ++i)
        fin >> prob[i];
    backtrack(1);
    ans /= cnt;
    fout << fixed << setprecision(6) << ans;
    return 0;
}