XChiChiX


這不是很戲劇化的發展嗎

e510: 10056 - What is the Probability?

  • 1294 字
  • 次閱讀
  • 則評論
  1. 1. 內容
  2. 2. 範例輸入
  3. 3. 範例輸出
  4. 4. 想法
  5. 5. 程式碼

CPE 一顆星選集 49 道必考題

題目連結:https://zerojudge.tw/ShowProblem?problemid=e510

內容

給定玩家數 N ，一個成功事件發生機率 p，玩家依序行動(不只一輪)，求第 i 個玩家成功的機率(有人成功即遊戲結束)。

第一列有一整數 S (S <= 1000)表示測資數，接著有三數分別為 N, p, i。

範例輸入

2
2 0.166666 1
2 0.166666 2

範例輸出

0.5455
0.4545

想法

完全沒有想法，於是跑去看大神教學。

看完之後，得到一個表格。

玩家 第一輪 第二輪 … 第R輪
1 (1-p) (1-p)^N * (1-p) (1-p)^N(R-1) * (1-p)
2 (1-p)^2 (1-p)^N * (1-p)^2 (1-p)^N(R-1) * (1-p)^2
… … … …
i (1-p)^(i-1) * p (1-p)^N * (1-p)^(i-1) * p (1-p)^N(R-1) * (1-p)^(i-1) * p
…
N

若要輪到第 i 個玩家，則前面必須都為失敗。
可以發現第 i 個玩家的成功機率為 p(i在第一輪成功) + p(i在第二輪成功) + … + p(i在第R輪成功)，是一個無窮等比級數，找出首項為 (1-p)^(i-1) * p，公比為 (1-p)^N。

即可利用公式 首項/(1-公比) 求解。

參考資料:YUI HUANG 演算法學習筆記

程式碼

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false), cin.tie(nullptr)
using namespace std;

int main(){
    fastio;
    int S, N, i;
    double p;
    cin >> S;
    while(S--){
        cin >> N >> p >> i;
        if(p == 0) {
            cout << "0.0000\n";
            continue;
        }
        double first = pow(1.0 - p, i - 1) * p;
        double r = pow(1.0 - p, N);
        cout << fixed << setprecision(4) << first / (1.0 - r) << "\n";
    }
}