Cod sursa(job #2507067)

Utilizator stefzahZaharia Stefan Tudor stefzah Data 9 decembrie 2019 16:09:15
Problema Dezastru Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <iomanip>

using namespace std;
int N, K;
double p[30];
double P[30], rez = 0, Pt = 1;
int st[30];
bool viz[30];
int ct;
bool mode;

void Back(int top) {
    if (top == K + 1) {
        if (mode == 0) {
            rez += P[top - 1];
            ct++;
        } else {
            rez += Pt / P[top - 1];
            ct++;
        }
        // cout << P << "\n";
    } else
        for (int i = st[top - 1]+1; i <= N-K+top; i++) {
            if (viz[i] == 0) {
                st[top] = i;
                viz[i] = true;
                P[top] = p[i] * P[top - 1];
                Back(top + 1);
                viz[i] = false;
            }
        }
}

int main() {
    ifstream fin("dezastru.in");
    ofstream fout("dezastru.out");
    fin >> N >> K;
    for (int i = 1; i <= N; i++) {
        fin >> p[i];
        Pt *= p[i];
    }
    P[0] = 1;
    if (K <= N / 2) {
        mode = 0;
        Back(1);
        fout << fixed << setprecision(6) << rez / (double) ct;
    } else {
        K = N - K;
        mode = 1;
        Back(1);
        fout << fixed << setprecision(6) << rez / (double) ct;
    }
}