Facebook 拼图(概率)

Question

下面是其中一个 facebook 谜题:我无法理解如何进行此操作。

你有 C 个容器、B 个黑球和无限数量的白球。您希望以一种方式在容器之间分配球，即每个容器至少包含一个球，并且选择白球的概率大于或等于 P%。选择是通过随机挑选一个容器，然后从中随机挑选一个球来完成的。

找到实现该目标所需的最少白球数。

输入

第一行包含 1 <= T <= 10 - 测试用例的数量。

以下 T 行中的每一行都包含三个整数 C B P，由一个空格分隔 1<= C <= 1000； 0 <= B <= 1000； 0 <= P <= 100；

输出

对于每个测试用例，输出一行包含一个整数——所需的最小白球数。 (测试将确保使用有限数量的球是可能的)

样本输入

3 
1 1 60 
2 1 60 
10 2 50 

样本输出

2 
2 
8 

解释

在第一个测试用例中，如果我们将 2 个白球和 1 个黑球放入盒子中，则选择白色球的概率为 66.(6)%，大于 60%

在第二个测试用例中，将一个白球放入一个盒子中，将白色+黑色放入另一个盒子中，得到 0.5 * 100% + 0.5 * 50% = 75%

对于第 3 个测试用例，请记住我们希望每个盒子中至少有一个球。

Answer 1

您可能必须执行以下操作:

初始编号白球数量 Nw = 1。

1. 给定白球的数量 Nw，找到给出最大概率拾取白球的配置。

2. 检查这个概率是否大于 P。

3. 如果是，那么 Nw 就是你的答案，否则，递增 Nw 并转到 1。

当然，挑战在于在第 1 步中找到最佳配置。

编辑:问题现在归结为给定的 W 个白球、B 个黑球和 C 个容器，找到能够最大概率拾取白球的配置。

P = ( w1/(w1+b1) + w2/(w2+b2) + ... + wc/(wc+bc) ) /c.
Max(P) = Max ( w1/(w1+b1) + w2/(w2+b2) + ... + wc/(wc+bc) )
Given: summation(wi) = W, summation(bi) = B, wi + bi >= 1

我猜测配置应该是这样的，如果有 N 个容器有白球，那么至少 N-1 应该只有 1 个白球而没有黑球，最多 1 个容器应该有白球和黑球.只是一个猜测...