soup-servings

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

There are two types of soup: type A and type B. Initially, we have <code>n</code> ml of each type of soup. There are four kinds of operations:

<ol>
	<li>Serve <code>100</code> ml of soup A and <code>0</code> ml of soup B,</li>
	<li>Serve <code>75</code> ml of soup A and <code>25</code> ml of soup B,</li>
	<li>Serve <code>50</code> ml of soup A and <code>50</code> ml of soup B, and</li>
	<li>Serve <code>25</code> ml of soup A and <code>75</code> ml of soup B.</li>
</ol>

When we serve some soup, we give it to someone, and we no longer have it. Each turn, we will choose from the four operations with an equal probability <code>0.25</code>. If the remaining volume of soup is not enough to complete the operation, we will serve as much as possible. We stop once we no longer have some quantity of both types of soup.

Note that we do not have an operation where all <code>100</code> ml&#39;s of soup B are used first.

Return the probability that soup A will be empty first, plus half the probability that A and B become empty at the same time. Answers within <code>10-5</code> of the actual answer will be accepted.

&nbsp;
Example 1:

<pre>
Input: n = 50
Output: 0.62500
Explanation: If we choose the first two operations, A will become empty first.
For the third operation, A and B will become empty at the same time.
For the fourth operation, B will become empty first.
So the total probability of A becoming empty first plus half the probability that A and B become empty at the same time, is 0.25 * (1 + 1 + 0.5 + 0) = 0.625.
</pre>

Example 2:

<pre>
Input: n = 100
Output: 0.71875
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>0 &lt;= n &lt;= 109</code></li>
</ul>

soupServings

Soup Servings

Math

Dynamic Programming

Probability and Statistics

有&nbsp;A&nbsp;和&nbsp;B 两种类型&nbsp;的汤。一开始每种类型的汤有&nbsp;<code>n</code>&nbsp;毫升。有四种分配操作：

<ol>
	<li>提供 <code>100ml</code> 的 汤A 和 <code>0ml</code> 的 汤B 。</li>
	<li>提供 <code>75ml</code> 的 汤A 和 <code>25ml</code> 的 汤B 。</li>
	<li>提供 <code>50ml</code> 的 汤A 和 <code>50ml</code> 的 汤B 。</li>
	<li>提供 <code>25ml</code> 的 汤A 和 <code>75ml</code> 的 汤B 。</li>
</ol>

当我们把汤分配给某人之后，汤就没有了。每个回合，我们将从四种概率同为 <code>0.25</code> 的操作中进行分配选择。如果汤的剩余量不足以完成某次操作，我们将尽可能分配。当两种类型的汤都分配完时，停止操作。

注意&nbsp;不存在先分配 <code>100</code> ml 汤B 的操作。

需要返回的值：&nbsp;汤A&nbsp;先分配完的概率 +&nbsp;&nbsp;汤A和汤B&nbsp;同时分配完的概率 / 2。返回值在正确答案&nbsp;<code>10-5</code>&nbsp;的范围内将被认为是正确的。

&nbsp;

示例 1:

<pre>
输入: n = 50
输出: 0.62500
解释:如果我们选择前两个操作，A 首先将变为空。
对于第三个操作，A 和 B 会同时变为空。
对于第四个操作，B 首先将变为空。
所以 A 变为空的总概率加上 A 和 B 同时变为空的概率的一半是 0.25 *(1 + 1 + 0.5 + 0)= 0.625。
</pre>

示例 2:

<pre>
输入: n = 100
输出: 0.71875
</pre>

&nbsp;

提示:

<ul>
	<li><code>0 &lt;= n &lt;= 109</code>​​​​​​​</li>
</ul>