DieRollingGame
2022 HF Qual · 2022-03-16 · by erinn
Problem Statement
You are playing a game in which you roll a single die, with faces numbered 1..n. With each roll, you score points equal to the value shown on the die. You keep rolling until you either reach total, and win, or else exceed total, and lose the game.
Assuming you are using a fair die that has an equal chance of landing on any side, what is the probability that you win the game?
Constraints
- n will be between 2 and 20.
- total will be between 1 and 100.
6 1 Returns: 0.16666666666666666
You're only going to make a single roll here, and you have a 1/6 chance of getting the 1.
4 2 Returns: 0.3125
Here, it's a little more interesting. You have a 1/4 chance of winning on the first roll, with a 2, as well as a 1/4 * 1/4 chance of winning with two rolls of 1.
2 3 Returns: 0.625
Since we're basically flipping a coin, we have an equal chance of rolling a 1 or a 2, leaving 1 or 2 more points that we need to win. We have a 1/2 chance to get 1 point, or a 3/4 chance to successfully score 2 points. 1/2 * 1/2 + 1/2 * 3/4 = 5/8
20 20 Returns: 0.12634750976878192
We could win this in a single roll of 20, 20 consecutive rolls of 1, or a whole lot of other possibilities in between.
20 100 Returns: 0.09523918142364225
Submissions are judged against all 10 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DieRollingGame with a public method double winChance(int n, int total) · 10 test cases · 2 s / 256 MB per case