Drolca

Apologize To Drolca
随笔 - 28, 文章 - 1, 评论 - 6, 引用 - 0
数据加载中……

pku 3744 Scout YYF I

#include <iostream>
#include 
<algorithm>
using namespace std;

const int maxn=12;
int n;
double p;
struct matrix
{
    
double m[2][2];
}
;
int mine[maxn];
matrix 
operator*(const matrix&a,const matrix&b)
{
    matrix tmp;
    
int i,j,k;
    
for(i=0;i<2;i++)
        
for(j=0;j<2;j++)
        
{
            tmp.m[i][j]
=0;
            
for(k=0;k<2;k++)
                tmp.m[i][j]
+=a.m[i][k]*b.m[k][j];
        }

    
return tmp;
}


matrix power(
int k)
{
    matrix tmp,res;
    matrix A;
    A.m[
0][0]=p,A.m[0][1]=1-p,A.m[1][0]=1,A.m[1][1]=0;
    matrix B;
    B.m[
0][0]=1,B.m[0][1]=0,B.m[1][0]=0,B.m[1][1]=1;
    
if(k==0)
        
return B;
    
if(k==1)
        
return A;
    
else 
    
{
        tmp
=power(k/2);
        res
=tmp*tmp;
        
if(k%2==1)
            res
=res*A;
        
return res;
    }

}


void slove(int n,double p)
{
    
double a=1,b=0;
    
int i;
    
for(i=0;i<n;i++)
        scanf(
"%d",&mine[i]);
    sort(mine,mine
+n);

    
double f2=1.0,f1=0.0;
    
int now=1;
    
for(i=0;i<n;i++)
    
{
        
if((mine[i]-1)-now>=0)
        
{
            matrix tmp
=power(mine[i]-1-now);
            f2
=(tmp.m[0][0]*f2+tmp.m[0][1]*f1)*(1-p);
            f1
=0;
            now
=mine[i]+1;
        }

        
else
        
{
            printf(
"%.7lf\n",0.0);
            
return;
        }

    }

    printf(
"%.7lf\n",f2);
}


int main()
{
    
while(scanf("%d %lf",&n,&p)!=EOF)
        slove(n,p);
    
return 0;
}


posted on 2009-10-05 18:48 Drolca 阅读(211) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理