Problem Statement
Beat the Star is a TV game show franchise started by the German original Schlag den Raab. In the game show a candidate attempts to beat a celebrity in a series of games. There are N games, numbered 1 to N. Each game has a winner and a loser. The winner of game X is awarded X points. The winner of the game show is the player (either the celebrity or the candidate) whose point total at the end is bigger.
In this problem we will make two simplifying assumptions (in comparison to the actual show):
- N will be such that the total number of points is odd, so that we do not have to handle ties.
- We will assume that all games always get played, even if the final winner is already known by that point.
You are soon going to take part in the game show as the candidate. The celebrity you'll compete against happens to be your twin. When trying to find an edge that would help you in the game, you watched many episodes of the show and you realized that the early games matter even less than it seems. Hence, you could save your strength by giving up some of the early games with the hope that this will help you beat your twin in the later games that are worth more points.
In this problem we want you to analyze how much each of the individual games matters. More precisely, we ask the following question: Assume that in each game each player wins with probability 50 percent. What is the probability that at the end game number G actually matters? (Given the full results of the show, game G matters if changing the winner of G would change the winner of the show.)
Definition
- Class:
- BeatTheStar
- Method:
- doesItMatter
- Parameters:
- int, int
- Returns:
- double
- Method signature:
- double doesItMatter(int N, int G)
- (be sure your method is public)
Notes
- The return value must have an absolute error at most 1e-9.
Constraints
- N will be between 1 and 100, inclusive.
- N will be such that the total number of points in the show is odd.
- G will be between 1 and N, inclusive.
Examples
2
1
Returns: 0.0
There are two games: game 1 awards one point and game 2 awards two. In this setting, game 1 does not matter at all: the winner of game 2 wins the show.
5
5
Returns: 0.625
If there are five games, game 5 matters quite often so winning it is crucial.
5
1
Returns: 0.125
Game 1 matters much less.
1
1
Returns: 1.0
2
2
Returns: 1.0
5
2
Returns: 0.125
Perhaps quite surprisingly, even though game 2 is worth twice as many points as game 1, in this particular format their importance is exactly the same.
9
7
Returns: 0.328125
98
98
Returns: 0.1393180923823675
98
47
Returns: 0.06629019390986395
98
1
Returns: 0.001407211300109263
97
97
Returns: 0.1400314813668493
97
93
Returns: 0.13414205765996984
97
42
Returns: 0.06012446724542525
97
2
Returns: 0.0028577070638482064
90
16
Returns: 0.025564159721327685
69
34
Returns: 0.08084554452270648
6
1
Returns: 0.0625
6
2
Returns: 0.1875
98
9
Returns: 0.012665942956824027
98
79
Returns: 0.11189929899765849
98
75
Returns: 0.1061636534901081
70
67
Returns: 0.1574558190463667
97
40
Returns: 0.05725134209699907
98
50
Returns: 0.07054288855858354
98
97
Returns: 0.13786704782636808
66
1
Returns: 0.0025311834339537143
98
93
Returns: 0.1320722598739415
98
45
Returns: 0.06345717488146932