http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1479. 猴子大战
时间限制:2.0s   内存限制:256.0MB   Special Judge
总提交次数:76   AC次数:19   平均分:36.05
将本题分享到:
   
 
问题描述
  小Q和小M最近发明了一种卡牌游戏,叫猴子大战。
  游戏最初小Q和小M各会获得一部分猴子牌。每局游戏,他们两个需要分别等概率地从自己的猴子牌中抽取一张进行战斗。获胜的一方将获得双方的猴子牌。如果一方获得了所有的猴子牌,则该方获得整场游戏的胜利。否则游戏将一直进行下去。
  在进行了若干场比赛以后,小Q和小M算出了一张胜率表,为每两张猴子牌之间进行战斗双方获胜的概率。由于每场战斗一定会决出胜负,而且胜率不受先后顺序影响,因此对于任意的两张猴子牌A和B,A战胜B的概率加B战胜A的概率为1。
  由于自己老是输给小M,小Q开始怀疑自己每次拿到的猴子牌是否能获得胜利。他希望求出自己拿到的每种猴子牌组合的获胜的概率。
  由于小Q接下来还有在CD市体育中心数以万计的运动计划,因此这个问题只能交给你来解决了。
输入格式
  输入的第一行包含两个正整数 n 和 m,表示猴子牌的总张数和需要求的猴子牌组合的个数。
  接下来有 n 行,每行包含 n 个实数,每个实数保留了两位小数。这 n 行中,其中第 i 行第 j 列的数为 P_(i,j),表示第 i 张猴子牌战胜第 j 张猴子牌的概率。保证P_(i,j)+P_(j,i)=1。特别地,P_(i,i)=0.5,没有特殊意义。
  最后有 m 行。每行包含一个长度为 n 的无空格分隔的01串,表示一个猴子牌的组合。其中第 i 个字符如果为0,表示最初第 i 张牌在小M处,否则表示在小Q处。
输出格式
  输出 m 行,每行一个实数,四舍五入保留八位小数,依次表示每个给定的猴子牌组合下小Q获胜的概率。
样例输入
3 4
0.50 0.60 0.40
0.40 0.50 0.70
0.60 0.30 0.50
110
011
111
000
样例输出
0.71304348
0.66086957
1.00000000
0.00000000
评分方法
  你的答案的每一行如果与我们给定的参考答案的差别均不超过2×10^(-6),则获得该测试点的得分,否则不得分。
  参考答案保证与真实值的差别不超过10^(-8),因此如果你输出的答案保证与真实值差别不超过2×10^(-6)-10^(-8),才能保证正确。
数据规模及约定
  对于每组数据,n的取值如下
测试点编号
n
测试点编号
n
1
n = 2
6
n = 20
2
n = 5
7
n = 40
3
n = 7
8
n = 60
4
n = 8
9
n = 80
5
n = 10
10
n = 100

  对于100%的数据,保证1≤n≤100,1≤m≤n^2。0≤P_(i,j)≤1,P_(i,j) 恰好包含2位小数,且 P_(i,j)+P_(j,i)=1。表示猴子牌组合的01串长度均为 n,且不含其它字符。
  P_(i,j )的生成方式为:在某个环境下,使用某个随机数种子,持续调用某语言生成整数的伪随机函数直到时钟函数达到1秒,接下来取连续的若干个随机函数值对101取模再除以100,作为输入数据中的满足 i<j 的 P_(i,j)。该生成过程只启动一次,即不会出现看到数据以后重新生成数据的情况。以上操作的目的是希望P_(i,j)的每个取值几乎等概率且不受人控制,你可以不必理会这段话。