1

以下は Facebook のパズルの 1 つです。これを進める方法がわかりません。

C 個の容器、B 個の黒玉、無制限の数の白玉が与えられます。すべてのコンテナーに少なくとも 1 つのボールが含まれ、白いボールを選択する確率が P パーセント以上になるように、コンテナー間でボールを分配します。選択は、容器をランダムに選び、続いてそこからボールを​​ランダムに選ぶことによって行われます。

それを達成するために最低限必要な白いボールの数を見つけてください。

入力

最初の行には 1 <= T <= 10 - テストケースの数が含まれます。

次の各 T 行には、1 つのスペースで区切られた 3 つの整数 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% を超えています。

2 番目のテストケースでは、1 つのボックスに 1 つの白いボールを入れ、別のボックスに白 + 黒を入れると、0.5 * 100% + 0.5 * 50% = 75% が得られます。

3 番目のテストケースでは、各ボックスに少なくとも 1 つのボールが必要であることを思い出してください。

4

1 に答える 1

0

おそらく、次のことを行う必要があります。

イニシャルNo. 白いボールの数 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 に答える