WeightedDice
Rookie SRM 12 · 2022-04-14 · by erinn
Problem Statement
You have a weighted (unfair) six-sided die. You know the probability of it landing on any of the six sides. You are given these probabilities in
You are going to play a game in which you repeatedly roll the die until the total of your rolls equals or exceeds the target value. If you reach the target value exactly, you win. If you exceed the target value, you lose.
Return the probability of winning the game.
Constraints
- prob will contain exactly 6 elmeents.
- The elements of prob will sum to 1.0.
- target will be between 1 and 100, inclusive.
{ 0.2, 0.2, 0.2, 0.2, 0.1, 0.1 }
1
Returns: 0.2
Here with a target of 1, we must get a 1 on the first roll in order to win. This happens with a probability of 0.2.
{ 0.2, 0.2, 0.2, 0.2, 0.1, 0.1 }
2
Returns: 0.24000000000000002
To score a 2, we can either roll a 2 on the first roll, with a probability 0.2, or else roll a 1, then another 1, with a probability 0.2 * 0.2 = 0.04. This gives us a total change of 0.2 + 0.04 = 0.24 of winning.
{ 1.0, 0.0, 0.0, 0.0, 0.0, 0.0 }
5
Returns: 1.0
In this scenario, our die will always roll a 1, thus we are guaranteed to win for any target value.
{ 0.5, 0.5, 0.0, 0.0, 0.0, 0.0 }
3
Returns: 0.625
We can get a total of 3 a few different ways: 1 + 2 (0.5 * 0.5 chance) 2 + 1 (0.5 * 0.5 chance) 1 + 1 + 1 (0.5 * 0.5 * 0.5 chance) 0.25 + 0.25 + 0.125 = 0.625
{ 0.5, 0.5, 0.0, 0.0, 0.0, 0.0 }
100
Returns: 0.6666666666666665
Submissions are judged against all 8 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class WeightedDice with a public method double winChance(vector<double> prob, int target) · 8 test cases · 2 s / 256 MB per case