That problem will be solved either by coefficient in binomial expansion ( polynomial multiplication )

i used the above , and also can be solvable with dynamic programming.

This is my correct code for third one :

#include<bits/stdc++.h>

#define ll unsigned long long

using namespace std;

vector<double> multiply(vector< double > A , vector< double > B){

int m = A.size();

int n = B.size();

vector< double > res(m + n - 1);

for(int i = 0 ; i < m + n - 1 ; ++i ) res[i] = 0;

for(int i = 0 ; i < m ; ++i )

for(int j = 0 ; j < n ; ++j )

res[i + j] += (A[i] * B[j]);

return res;

}

double coeficient(int X , int Y , int S){

vector< double > res;

vector< double > A;

res.push_back(1);

A.push_back(0);

for(int i = 1 ; i <= Y ; ++i )

A.push_back(1.0/Y);

while(X){

if(X & 1)

res = multiply(res , A);

X = X >> 1;

A = multiply(A , A);

}

double ans = 0;

S = max(0 , S);

for(int i = S ; i < res.size() ; ++i )

ans += res[i];

return ans;

}

int main(){

cin.sync_with_stdio(false);

freopen("a.txt","r",stdin);

freopen("b.txt","w",stdout);

int T , tt = 1;

cin >> T;

while(T--){

int N , S ;

cin >> S >> N;

double ans = 0.0;

for(int i = 1 ; i <= N ; ++i ){

string x;

cin >> x;

int X = 0;

if(x[1] == 'd')

X = (x[0] - '0') ; else

X = (x[0] - '0') * 10 + (x[1] - '0');

int idx = -1;

if(x[1] == 'd')

idx = 2; else

idx = 3;

int Y = 0;

if(idx + 1 == x.size())

Y = x[idx] - '0'; else {

if(x[idx + 1] >= '0' && x[idx + 1] <= '9')

Y = (x[idx] - '0') * 10 + (x[idx + 1] - '0'); else

Y = x[idx] - '0';

}

int Z = 0;

for(int j = 0 ; j < x.size() ; ++j ){

if(x[j] == '+' || x[j] == '-'){

for(int k = j + 1 ; k < x.size() ; ++k )

Z = Z * 10 + (x[k] - '0');

if(x[j] == '-')

Z = -Z;

break;

}

}

int s = S - Z;

double res = coeficient(X , Y , s );

ans = max(ans , res);

}

printf("Case #%d: %.7lf\n",tt++, ans);

}

return 0;

}