UVa 10056 : What is the Probability?
問題リンク:http://uva.onlinejudge.org/external/100/10056.html
問題概要:
N人のプレイヤーがいる
プレイヤーは1から順にNまで番号付けされており、
プレイヤー1から順にサイコロらしきものをふる
サイコロらしきものは確率pで目的の目を出す
目的の目がでたとき、そのプレイヤーの勝利となる
N人目のプレイヤーがサイコロらしきものを振っても勝負がつかない場合は
再度プレイヤー1からサイコロらしきものを振りなおす
プレイヤーIが勝利する確率を求めよ
解法:
プレイヤーIが1回目で勝利する確率は(1-p)^(I-1) * p ( <= 自分の前のプレイヤーが全て目的の目でない目をだし、自分は目的の目を出す確率)
プレイヤーIが2回目で勝利する確率は(1-p)^(I-1 + N) * p
プレイヤーIが3回目で勝利する確率は(1-p)^(I-1 + 2*N) * p
...
なので、初項が(1-p)^(I-1) * p
公比が(1-p)^Nの無限等比級数となる
よって答えとなる確率はこの和なので
( ( ( 1 - p ) ^ ( I - 1 ) ) * p ) / ( 1 - ( ( 1 - p ) ^ N ) ) となる
注意点
目的の目がでる確率pが0である場合は上記の式では答えがでない
この場合勝利する確率は0となる
実装時間:
5分
コード:
/* 01:40 - 01: 45 */ #include<iostream> #include<cmath> #include<cstdio> using namespace std; int main(){ int S; cin >> S; while(S--){ long double N,p,I; cin >> N >> p >> I; if(p == 0.0) puts("0.0000"); else printf("%.4Lf\n",(pow(1.0-p,I-1)*p)/(1.0-(pow(1.0-p,N)))); } return 0; }