Cod sursa(job #2173268)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 15 martie 2018 21:24:16
Problema Dezastru Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define mp make_pair
#define CHECK(x) if(!(x)) return false;
typedef pair<int, int> pii;

#ifdef INFOARENA
#define ProblemName "dezastru"
#endif

#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif

const int MAXN = 30;
int p[MAXN];
int N, K;

const int MAGIC = 100000000;

LL bkt(int l, int lastidx, LL cur) {
  if (l == K)
    return cur;
  LL s = 0;
  for (int i = lastidx + 1, lim = N + 1 - (K - l); i <= lim; ++i)
    s += bkt(l + 1, i, cur * p[i] / MAGIC);
  return s;
}

int main() {
  assert(freopen(InFile, "r", stdin));
  assert(freopen(OuFile, "w", stdout));
  scanf("%d%d", &N, &K);
  for (int i = 0; i < N; ++i) {
    double tmp;
    scanf("%lf", &tmp);
    p[i] = (int)(tmp * MAGIC);
  }
  double rez = 1.0 * bkt(0, -1, 1 * MAGIC) / MAGIC;
  for (int i = 2; i <= N - K; ++i)
    rez *= i;
  for (int i = K + 1; i <= N; ++i)
    rez /= i;
  printf("%.6lf\n", rez);
  return 0;
}