Cod sursa(job #1828451)

Utilizator KanghuAndre Popescu Kanghu Data 13 decembrie 2016 13:21:35
Problema Dezastru Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 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];

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

        for(int a = 0; a < x; a++)
        {
            k = k * C[M[a]];
        }

        r = r + k;

        for(int a = 2; a < M[1]; a++)
        {
            nr++;
            k = k / C[M[0]];
            M[0] = a;
            k = k * C[a];
            r = r + k;
        }

        M[0] = 1;
        return;
    }

    else
    {
        for(int a = M[x - 1] + 1; a <= N; a++)
        {

            if(V[a] != -1)
            {
                M[x] = V[a];
                V[a] = -1;

                backtrack(x + 1);

                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[0] = 1;

    backtrack(1);

    o << r / nr;

    return 0;
}