1

以下是 Facebook 难题之一：我无法理解如何进行此操作。

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

找到实现这一目标所需的最少白球数量。

输入

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

以下 T 行中的每一行包含三个整数 CBP，由单个空格分隔 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%

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

4

1 回答 1

0

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

初始编号 白球数 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 个容器应该有白球和黑球。虽然只是猜测...

于 2013-08-27T16:10:06.533 回答