e510 - 10056 - What is the Probability?

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算在一個循環遊戲中，特定玩家獲勝的機率。遊戲中，每個玩家輪流嘗試一個成功事件，成功機率為 p。遊戲持續進行直到有人成功，獲勝者是第一個成功的人。題目給定玩家數量 N，成功機率 p，以及目標玩家的編號 i，要求計算第 i 個玩家獲勝的機率。

解題思路

這題可以透過模擬的方式來計算機率。由於遊戲是循環的，我們可以模擬多次遊戲，並記錄第 i 個玩家獲勝的次數。然後，用第 i 個玩家獲勝的次數除以總的遊戲次數，即可得到第 i 個玩家獲勝的機率。

然而，直接模擬次數過多可能會導致時間超時。因此，我們可以利用數學公式來簡化計算。第 i 個玩家獲勝的機率可以表示為：

P(第 i 個玩家獲勝) = p + (1-p) * (1-p) * ... * (1-p) * p (共 i-1 個 (1-p))

更精確地說，第 i 個玩家獲勝的機率是，前 i-1 個玩家都失敗，然後第 i 個玩家成功。由於遊戲是循環的，我們可以將這個機率表示為一個無限級數。

程式碼中，使用一個迴圈來計算這個無限級數的前幾項，直到項的值小於一個很小的數 (0.000001) 為止。這樣可以有效地近似計算出第 i 個玩家獲勝的機率。

複雜度分析

• 時間複雜度: O(100000) (迴圈次數受限於 100000)
• 空間複雜度: O(1) (只使用了常數個變數)

程式碼

#include <iostream>
#include <iomanip>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	int n,a,b;
	cin >> n;
	double p,ans;
	while(n--){
		cin >> a >> p >> b;
		ans=0;
		double op=1,tmp=1-p,dp=1;
		for(int i=0;i<a;++i)
			dp*=tmp;
		for(int i=1;i<b;++i)
			op*=tmp;
		for(int k=0;k<=100000;++k){
			ans+=p*(op);
			op*=dp;
			if(op<=0.000001)break;
		}
		cout << fixed  <<  setprecision(4) << ans << "\n";
	}
}