Cod sursa(job #2173384)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 15 martie 2018 21:59:24
Problema Dezastru Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include<stdio.h>

#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;
const int BITS = 25;
int p[MAXN];
int N, K;
int rez;
int cur;
int st[MAXN];

void bkt(int l) {
  int bak_cur;
  if (l == K) {
    rez += cur;
    return;
  }
  for (int i = st[l] + 1; i + (K - l - 1) <= N; ++i) {
    bak_cur = cur;
    cur = (int)((1LL * cur * p[i - 1]) >> BITS);
    st[l + 1] = i;
    bkt(l + 1);
    cur = bak_cur;
  }
}

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