Problem statement
Two friends Kunal and Satyam are playing an interesting game. They take turns drawing a ball from a bag which initially contains R red balls and G green balls. Each player draws a ball alternatively and never put it back. The person who is the first to draw a red balls wins. Satyam always draws first. If there are no more balls in the bag and nobody has drawn a red ball, the satyam wins.
Input -----
The first line will contain the number of test cases T. The first line of each test case will contain a number R (number of red balls) and G(number of green balls )
Cases:
2 1 --> 0.6666667 1 1 ---> 0.50000 10 0 ----> 1.0000
problem link is here:
I tired to solve the problem using top-bottom approach but my codes gives wrong answer at the last case (0 instead of 1)
int probability = 0, c = 0;
void magic(int red, int green, int turn){
if(green == -1 || red == -1)return ;
if(red == 0){
probability++;
if(turn % 2 == 0) c++;
return ;
}
if(turn == -1) turn = 0;
else turn++;
magic(red, green-1, turn % 2);
magic(red-1, green, turn % 2);
return ;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(nullptr);
int q;
cin >> q;
while(q--){
int x, y;
cin >> x >> y;
magic(x, y, -1);
cout << fixed << setprecision(9) << c * 1.0 / probability << '\n';
probability = 0, c = 0;
}
return 0;
}
I will appreciate any kind of help from all of you, and thanks for your time
if you want to use dp
include <bits/stdc++.h>
using namespace std; int dp[1000005]; int cnt = 0; long double r , b; int solve(int red , int blue){ if(!red&&!blue)return 0; if(dp[red]!=-1) return dp[red]; else{ if(red)return dp[red] = solve(red-1,blue)+1; if(blue)return solve(red,blue-1); } } int main() { memset(dp,-1,sizeof(dp)); cin>>r>>b; cout<<(long double)solve(r,b)/(r+b); return 0; }
and there is a math solution red/(red+blue)
It gives wrong answer :(