SingleOrDouble
2022 TCO Parallel 1A · 2022-04-14 · by misof
Problem Statement
"What's more likely? A single A, or a double B?"
This is the question Alice and Bob have been pondering since early morning today.
Let's explain what's going on. Alice and Bob are generating a sequence of random numbers. Each number is generated by rolling N standard D-sided dice and summing up the values rolled.
(A standard D-sided die has D faces with numbers 1 to D on them. Whenever the die is rolled, each face will come up with probability 1 / D.)
Alice wins as soon as the value A appears in the sequence. Bob wins if the value B appears in the sequence twice in a row. As soon as either player wins, the game is over.
For example, suppose A=2 and B=7. If the sequence of numbers starts 4, 7, 11, 7, 5, 2, ... after the sixth number Alice wins the game.
(Note that Bob did not win after the fourth number: the number 7 did appear twice, but the appearances were not consecutive.)
Given the
Notes
- The return value must have an absolute error at most 10^(-6) to be accepted.
- All rolls of dice are mutually independent.
Constraints
- N will be between 1 and 10, inclusive.
- D will be between 2 and 10, inclusive.
- A will be between N*1 and N*D, inclusive.
- B will be between N*1 and N*D, inclusive.
- A will not be equal to B.
1 2 1 2 Returns: 0.75
Each number is generated by rolling a single two-sided die - in other words, by flipping a coin with "1" on one side and "2" on the other side. Alice is waiting for a single 1. Bob is waiting for a double 2. If either of the first two throws is a 1, Alice wins. If both are 2, Bob wins. In either case the game will be over after at most two throws.
1 6 1 2 Returns: 0.8749999999999999
Same game as in Example 0, but now with a standard 6-sided die. Alice is still a strong favorite in this game. Intuitively, Bob getting a single 2 has the same probability as Alice getting a single 1, and thus Bob getting a double 2 before Alice getting a single 1 must be very unlikely. However, with a six-sided die the players can sometimes generate numbers other than 1 and 2, and it can sometimes take very many turns until one of the players wins. This influences our answer - you may note that the return value in this test case differs from the return value in Example 0.
2 6 2 7 Returns: 0.5384615384615384
Two standard dice are used to generate the numbers. Alice is waiting for a single appearance of the least likely number (2), Bob is waiting for two consecutive appearances of the most likely number (7). It turns out that this game is almost fair, Alice only has a tiny edge over Bob.
3 10 29 16 Returns: 0.36440677966101687
Here the value Alice wants is so unlikely that Bob is actually the favorite to win the game, even though he's waiting for a double.
10 2 15 10 Returns: 0.9999961285477021
Submissions are judged against all 69 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SingleOrDouble with a public method double probAlice(int N, int D, int A, int B) · 69 test cases · 2 s / 256 MB per case