Cod sursa(job #3296783)

Utilizator urweakurweak urweak Data 17 mai 2025 00:36:20
Problema Dezastru Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <math.h>
#include <iomanip>

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

double v[25];
int N, K;
int stack[25];
bool checked[25];
double result = 0;
int comb = 0;

// recursive backtracking or iterative backtracking
double calculateProbability()
{
    double prob = 1.0;
    for(int i = 0; i<K; i++)
    {
        prob*=v[stack[i]]; 
    }
    return prob;
}


void permutations(int level)
{
    if(level == K)
    {
        // out << calculateProbability() << std::endl;
        result+=calculateProbability();
        comb++;
        return;
    }
    
    for(int i = 0; i<N; i++)
    {
        if(checked[i]) continue;
        stack[level] = i;
        checked[i] = true;
        permutations(level+1);
        checked[i] = false;   
    }
}

int main()
{
    in >> N >> K;
    for(int i = 0; i<N; i++)
    {
        in >> v[i];
    }
    permutations(0);
    out << std::fixed << std::setprecision(6) << result/comb;
}