Field Trip-FTRIP

Problem Link

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 1001;
double ncr[N][N];

void calNCR()
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
            ncr[i][j] = 0;
    }

    for(int i = 0; i < N; i++)
    {
        ncr[i][0] = ncr[i][i] = 1.0;
        for(int j = 1; j < i; j++)
        {

            ncr[i][j] = ncr[i - 1][j - 1] + ncr[i - 1][j];
        }
    }
}

int main()
{
    int t, s, n, m, k;

    calNCR();
    cin >> t;
    for(int j = 0; j < t; j++)
    {
        cin >> s >> n >> m >> k;

        double den = ncr[s - 1][n - 1];
        double num = 0;

        /* if s = 6, m = 4, n = 4, k = 1. Here 2 people from m will go to the trip for sure.
           One of them is Alice, so one more friend will picked up for sure. So we should start checking              probability of picking from 2(mc2) because 1 will be picked up for sure
            so start i from max(k, n - 1 + m - s)  instead of k
        */

        for(int i = max(k, n - 1 + m - s); i <= min(m - 1, n - 1); i++)
        {
            num += (ncr[m - 1][i] * ncr[s - m][n - i - 1]);
        }
        printf("%.9lf\n", num/den);
    }
    return 0;
}