solution of https://algospot.com/judge/problem/read/SNAIL

snail.cpp

//https://algospot.com/judge/problem/read/SNAIL
//timecomplexity : O(2m-n)
#include <stdio.h>
#include <math.h>

/*
int factorial(int a) {
  int result = 1;
  for (int i = a; i >= 1; i--) {
    result *= i;
  }

  return result;
}

double combination(int a, int b) {
  printf("check comb : %.10f\n", factorial(a) / (factorial(a - b) * factorial(b)));

  return factorial(a) / (factorial(a - b) * factorial(b));
}
*/

double getProb(int allDay, int winDay) {
  // combination(allDay, winDay) * 0.75^winDay * 0.25^(allDay - winDay)
  double retVal = 1.0;

  for (int i = allDay, j = winDay; i > allDay - winDay; i--, j--) {
    retVal = (retVal * i * 0.75) / j;
  }
 
  retVal /= pow(4.0, allDay - winDay);

  return retVal;
}

int main(void) {
  int T;

  scanf("%d\n", &T);

  while (T-- > 0) {
    int n = 0, m = 0;
    int winDay = 0;
    double prob = 0.0;

    scanf("%d %d", &n, &m);

    winDay = n - m;
    for (int i = winDay; i <= m; i++) {
      prob += getProb(m, i);
    }
    printf("%.10f\n", prob);
  }

  return 0;
}