Problem Statement
This problem references two cards from a real trading card game. No knowledge of the game is needed to solve the problem.
Delina, Wild Mage, has the following ability:
- Whenever Delina attacks:
- Choose a creature you control.
- Roll a d20. (See Notes.)
- Create a copy of the chosen creature.
- If you rolled T or more, go to step 2.
Pixie Guide has the following ability:
- If you would roll one or more dice, instead roll that many dice plus one and ignore the lowest roll.
The effect of Pixie Guides is cummulative. For example, if you have three Pixie Guides and you were supposed to roll a single die, you will instead roll four such dice and take the maximum of the values you rolled. (In other words, you added an extra die three times and then you ignored the lowest roll three times.)
You have G Pixie Guides. You let Delina attack. Her ability is activated. In step 1, you choose one of your Pixie Guides.
Calculate and return the probability of rolling dice forever.
Definition
- Class:
- Delina
- Method:
- getProbability
- Parameters:
- int, int
- Returns:
- double
- Method signature:
- double getProbability(int T, int G)
- (be sure your method is public)
Notes
- A d20 is a 20-sided regular die. When you roll it, you will get one of the numbers 1 to 20 chosen uniformly at random.
- Your return value will be accepted if it has an absolute error at most 10^(-9).
Constraints
- T will be between 1 and 20, inclusive.
- G will be between 1 and 100, inclusive.
Examples
15
1
Returns: 0.14105299128211796
This is the original version of Delina: we repeat the process if we roll 15 or more. We start with a single Pixie Guide to help us. Sometimes the process terminates. For example, it may look as follows: Step 1: We choose the only Pixie Guide we have. Step 2: We roll a 12 and a 7. (Remember that we already have one Pixie Guide, so we roll two dice instead of one. We then ignore the 7 as the lowest roll, and we take the 12 as the result of the roll.) Step 3: We create a copy of the chosen Pixie Guide. (We now have two of them.) Step 4: The threshold is T = 15, which is more than the 12 we rolled. Thus, nothing more happens. Some other time the process could look as follows: Step 1: We choose the only Pixie Guide we have. Step 2: We roll 17 and 1. (The result of the roll is 17.) Step 3: We create a copy of the chosen Pixie Guide. (We now have two of them.) Step 4: We check that 17 >= 15, so we return to step 2 and continue from there. Step 2: We roll 9, 9, 15. (Note that we now have two pixies, so we roll three dice. We then ignore the 9 and the other 9, and we take the 15 as the outcome.) Step 3: We create a second copy of the original Pixie Guide. (Now we have three.) Step 4: As 15 >= 15, we return to step 2. Step 2: We roll 2, 4, 2, 4. (Result: 4.) Step 3: We create another Pixie Guide. Step 4: As 4 < 15, the process terminates. However, in some other cases the process will actually continue forever. As it goes on, we get more and more pixies, and that makes it less and less likely to ever fail to hit the threshold. Approximately one in seven times we are going to produce more and more pixies without ever stopping.
15
2
Returns: 0.2765744927100352
Starting with two pixies makes the infinite scenario much more likely.
1
7
Returns: 1.0
For T = 1 termination is literally impossible, each attempt goes infinite.
20
100
Returns: 0.8934609022461157
With T = 20 restarting the process is as unlikely as possible, but a starting army of 100 pixies still makes the infinite outcome very likely.
20
97
Returns: 0.876845719380737
19
98
Returns: 0.9997049145998269
18
97
Returns: 0.9999991928331824
19
43
Returns: 0.9073509297957283
17
22
Returns: 0.970869393209567
15
3
Returns: 0.42096574232882067
15
69
Returns: 0.9999999999521655
14
32
Returns: 0.9999980854249401
12
17
Returns: 0.999952868785191
11
13
Returns: 0.9998779346544671
10
10
Returns: 0.9997214280320604
10
77
Returns: 1.0
9
99
Returns: 1.0
1
1
Returns: 1.0
1
100
Returns: 1.0
2
1
Returns: 0.9973687508223682
2
2
Returns: 0.9998684218770608
2
3
Returns: 0.9999934210546927
2
4
Returns: 0.9999996710526368
2
5
Returns: 0.9999999835526316
2
6
Returns: 0.9999999991776316
3
3
Returns: 0.9998888900112223
4
4
Returns: 0.9999106628057459
5
6
Returns: 0.9999840000426666
5
21
Returns: 0.9999999999999994