Cod sursa(job #1827724)

Utilizator KanghuAndre Popescu Kanghu Data 12 decembrie 2016 11:02:09
Problema Dezastru Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
#include <iostream>

using namespace std;

double r;
int nr;

int N, K;
int V[26];
int M[26];
double C[26];
double D[26][26];
double k = 1.0;

void backtrack(int x)
{
    if(x == K)
    {
        nr++;

        r = r + k;
        return;
    }

    else
    {
        for(int a = M[x - 1]; a <= N; a++)
        {
            if(V[a] != -1)
            {
                double b = k;
                M[x] = V[a];
                V[a] = -1;

                k = k * C[M[x]];
                backtrack(x + 1);
                k = b;

                V[a] = M[x];
            }
        }
    }
}

int main()
{
    ifstream i("dezastru.in");
    ofstream o("dezastru.out");

    i >> N >> K;

    for(int a = 1; a <= N; a++)
    {
        i >> C[a];
    }

    for(int a = 0; a <= N; a++)
    {
        V[a] = a;
    }

    M[-1] = 1;

    backtrack(0);

    o << r / nr;

    return 0;
}