Problem B
Dynamic Programming: Winning Streak
In this task, you will write a problem that solves the following computational problem. See the lab instructions for further details.
You are playing a game against a friend. The game involves both chance and skill, and depending on your skill level relative to your friend’s, there is some probability $p$ that you will win the game (e.g. $p=1$ means you are so much better than your friend that you always win, $p=1/2$ means you and your friend are equally good and have the same chance of winning, and if $p=0.01$ then your friend is much better than you but you sometimes win). The game is fun and you play it over and over again, each time winning the game with the same probability $p$, independently for each game.
The web site on which you are playing gives various forms of achievements and badges to encourage engagement. You currently have your mind set on obtaining the “winning streak” achievement, which requires winning $k$ games in a row (for some parameter $k$).
Write a program that computes, given the total number of games $n$ that you will play, what the probability is that you will obtain the winning streak achievement.
Input
The input consists of three numbers, each on a separate line:
-
The integer $n$, the total number of games you play in a day.
-
The integer $k$ ($2 \le k \le n$), the number of games in a row you need to win.
-
The real number $p$ ($0 \le p \le 1$), the probability of winning each game.
Output
Output the probability that after playing $n$ games, you at some point won at least $k$ games in a row.
The exact formatting of your answer is not important, and it will be considered correct if it is within $10^{-6}$ of the correct answer (so if you print your answer with more than $6$ decimal digits you should not have any issues).
| Sample Input 1 | Sample Output 1 |
|---|---|
4 2 0.7 |
0.784 |
| Sample Input 2 | Sample Output 2 |
|---|---|
20 4 0.42 |
0.2922575722241294 |
