PKU 3744 Scout YYF I
http://poj.org/problem?id=3744
直線上に地雷がばらまかれている場所を通り抜ける。
ここで最初は1の位置にいて、移動毎に確率pで1進み、確率1-pで2進む。
地雷の場所が分かっているとき、無事に通り抜けられる確率を求めろというような問題。
確率漸化式で丁度n番目の位置に止まるような確率を求めて、そこから地雷をまたぐように渡れる確率をかけていって答えを出しました。
typedef struct _mat{ double el[2][2]; _mat(double p00,double p10,double p01,double p11){ el[0][0]=p00; el[1][0]=p10; el[0][1]=p01; el[1][1]=p11; } _mat(){ rep(i,2)rep(j,2)el[i][j]=0; } _mat operator*(const _mat&r){ _mat ret; rep(i,2)rep(j,2){ rep(k,2)ret.el[i][j]+=this->el[i][k]*r.el[k][j]; } return ret; } }mat; mat pn; mat pow(int n){ if(n==0)return mat(1,0,0,1); mat ret=pow(n/2); ret=ret*ret; if(n%2)ret=ret*pn; return ret; } int in[11]; main(){ int n; double p; while(cin>>n>>p){ rep(i,n)cin>>in[i]; in[n++]=0; sort(in,in+n); pn.el[0][0]=p; pn.el[0][1]=1-p; pn.el[1][0]=1; pn.el[1][1]=0; double ans=1; for(int i=1;i<n;++i){ int dd=in[i]-in[i-1]-1; if(dd<1){ ans=0; break; } ans*=pow(dd).el[1][0]*(1-p); } printf("%.7f\n",ans); } }