Need for Pink Slips
Contest: Codeforces Round 730 (Div. 2)
Difficulty rating: 1900
Tags: bitmasks, brute force, dfs and similar, implementation, math, probabilities

After defeating a Blacklist Rival, you get a chance to draw $$$1$$$ reward slip out of $$$x$$$ hidden valid slips. Initially, $$$x=3$$$ and these hidden valid slips are Cash Slip, Impound Strike Release Marker and Pink Slip of Rival's Car. Initially, the probability of drawing these in a random guess are $$$c$$$, $$$m$$$, and $$$p$$$, respectively. There is also a volatility factor $$$v$$$. You can play any number of Rival Races as long as you don't draw a Pink Slip. Assume that you win each race and get a chance to draw a reward slip. In each draw, you draw one of the $$$x$$$ valid items with their respective probabilities. Suppose you draw a particular item and its probability of drawing before the draw was $$$a$$$. Then,

- If the item was a Pink Slip, the quest is over, and you will not play any more races.
- Otherwise,   If $$$a\leq v$$$, the probability of the item drawn becomes $$$0$$$ and the item is no longer a valid item for all the further draws, reducing $$$x$$$ by $$$1$$$. Moreover, the reduced probability $$$a$$$ is distributed equally among the other remaining valid items.  If $$$a > v$$$, the probability of the item drawn reduces by $$$v$$$ and the reduced probability is distributed equally among the other valid items.

For example,

- If $$$(c,m,p)=(0.2,0.1,0.7)$$$ and $$$v=0.1$$$, after drawing Cash, the new probabilities will be $$$(0.1,0.15,0.75)$$$.
- If $$$(c,m,p)=(0.1,0.2,0.7)$$$ and $$$v=0.2$$$, after drawing Cash, the new probabilities will be $$$(Invalid,0.25,0.75)$$$.
- If $$$(c,m,p)=(0.2,Invalid,0.8)$$$ and $$$v=0.1$$$, after drawing Cash, the new probabilities will be $$$(0.1,Invalid,0.9)$$$.
- If $$$(c,m,p)=(0.1,Invalid,0.9)$$$ and $$$v=0.2$$$, after drawing Cash, the new probabilities will be $$$(Invalid,Invalid,1.0)$$$.

You need the cars of Rivals. So, you need to find the expected number of races that you must play in order to draw a pink slip.

Input format:
The first line of input contains a single integer $$$t$$$ ($$$1\leq t\leq 10$$$)  — the number of test cases.

The first and the only line of each test case contains four real numbers $$$c$$$, $$$m$$$, $$$p$$$ and $$$v$$$ ($$$0 < c,m,p < 1$$$, $$$c+m+p=1$$$, $$$0.1\leq v\leq 0.9$$$).

Additionally, it is guaranteed that each of $$$c$$$, $$$m$$$, $$$p$$$ and $$$v$$$ have at most $$$4$$$ decimal places.

Output format:
For each test case, output a single line containing a single real number — the expected number of races that you must play in order to draw a Pink Slip.

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
For the first test case, the possible drawing sequences are:

- P with a probability of $$$0.6$$$;
- CP with a probability of $$$0.2\cdot 0.7 = 0.14$$$;
- CMP with a probability of $$$0.2\cdot 0.3\cdot 0.9 = 0.054$$$;
- CMMP with a probability of $$$0.2\cdot 0.3\cdot 0.1\cdot 1 = 0.006$$$;
- MP with a probability of $$$0.2\cdot 0.7 = 0.14$$$;
- MCP with a probability of $$$0.2\cdot 0.3\cdot 0.9 = 0.054$$$;
- MCCP with a probability of $$$0.2\cdot 0.3\cdot 0.1\cdot 1 = 0.006$$$.

For the second test case, the possible drawing sequences are:

- P with a probability of $$$0.4$$$;
- CP with a probability of $$$0.4\cdot 0.6 = 0.24$$$;
- CMP with a probability of $$$0.4\cdot 0.4\cdot 1 = 0.16$$$;
- MP with a probability of $$$0.2\cdot 0.5 = 0.1$$$;
- MCP with a probability of $$$0.2\cdot 0.5\cdot 1 = 0.1$$$.

So, the expected number of races is equal to $$$1\cdot 0.4 + 2\cdot 0.24 + 3\cdot 0.16 + 2\cdot 0.1 + 3\cdot 0.1 = 1.86$$$.

Example input:
4
0.2 0.2 0.6 0.2
0.4 0.2 0.4 0.8
0.4998 0.4998 0.0004 0.1666
0.3125 0.6561 0.0314 0.2048

Example output:
1.532000000000
1.860000000000
5.005050776521
4.260163673896

Editorial:
Bruteforce over all the possible drawing sequences until we are sure to get a pink slip, i.e., until the probability of drawing a pink slip becomes $$$1$$$.
Let's see why this works.
Whenever we draw a reward other than a pink slip,
• If $$$a\leq v$$$, one of the rewards becomes invalid, reducing $$$x$$$ by $$$1$$$ and this can happen at most $$$2$$$ times during the whole process.
• Else, the probability of drawing a pink slip increases by $$$\dfrac{v}{2}$$$.
Notice that the probability of drawing a pink slip can never decrease.
Now, since $$$v\geq 0.1$$$, each time we make a draw of the second type, the probability of drawing a pink slip increases by at least $$$0.05$$$. It will reach $$$1$$$ after just $$$20$$$ such draws. So, there will be at most $$$d=22$$$ draws before we are sure to get a pink slip.
Simulating the whole process will take $$$\mathcal{O}(2^d)$$$ time which is sufficient in our case. What's left is just implementing the bruteforce solution taking care of precision errors while dealing with floating point numbers, especially while comparing $$$a$$$ with $$$v$$$ as this can completely change things up, keeping an item valid when it should become invalid. It follows that an error approximation of 1e-6 is sufficient while comparing any two values because all the numbers in the input have at most $$$4$$$ decimal places.
Time Complexity - $$$\mathcal{O}\big(2^{\frac{2}{v}}\big)$$$.