Lucky Coins

题目连接:

http://acm.hdu.edu.cn/showproblem.php?pid=5985

Description

Bob has collected a lot of coins in different kinds. He wants to know which kind of coins is lucky. He finds out a lucky kind of coins by the following way. He tosses all the coins simultaneously, and then removes the coins that come up tails. He then tosses all the remaining coins and removes the coins that come up tails. He repeats the previous step until there is one kind of coins remaining or there are no coins remaining. If there is one kind of coins remaining, then this kind of coins is lucky. Given the number of coins and the probability that the coins come up heads after tossing for each kind, your task is to calculate the probability for each kind of coins that will be lucky.

Input

The first line is the number of test cases. For each test case, the first line contains an integer k representing the number of kinds. Each of the following k lines describes a kind of coins, which contains an integer and a real number representing the number of coins and the probability that the coins come up heads after tossing. It is guaranteed that the number of kinds is no more than 10, the total number of coins is no more than 1000000, and the probabilities that the coins come up heads after tossing are between 0.4 and 0.6.

Output

For each test case, output a line containing k real numbers with the precision of 6 digits, which are the probabilities of each kind of coins that will be lucky.

Sample Input

3

1

1000000 0.5

2

1 0.4

1 0.6

3

2 0.4

2 0.5

2 0.6

Sample Output

1.000000

0.210526 0.473684

0.124867 0.234823 0.420066

Hint

题意

有一堆硬币,每回合为正面的概率为P,每回合我们都会去掉当前翻面为反面的硬币。

问每种硬币剩到只剩下一个的概率是多少。

保证 0.4<P<0.6

题解:

给了概率的范围,显然这道题就是模拟扔就行了,随便扔个几十回合,这个概率就会降到很小的范围。

第i个硬币第j回合全死掉的概率为 (1-Pj)num[i]

活下来的概率当然是1-死掉的。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 15;
int n;
double num[maxn],ans[maxn],p[maxn];
double count_die(int x,int y){
return pow(1-pow(p[x],y),num[x]);
}
double count_live(int x,int y){
return 1-count_die(x,y);
}
void solve(){
scanf("%d",&n);
memset(ans,0,sizeof(ans));
for(int i=0;i<n;i++)
cin>>num[i]>>p[i];
if(n==1){
printf("1.000000\n");
return;
}
for(int i=1;i<100;i++){
for(int j=0;j<n;j++){
double tmp = 1;
for(int k=0;k<n;k++){
if(k==j)continue;
tmp*=count_die(k,i);
}
ans[j]+=(count_live(j,i)-count_live(j,i+1))*tmp;
}
}
for(int i=0;i<n;i++)
if(i==0)printf("%.6f",ans[i]);
else printf(" %.6f",ans[i]);
printf("\n");
}
int main(){
int t;
scanf("%d",&t);
while(t--)solve();
}

最新文章

  1. MVC学习随笔----如何在页面中添加JS和CSS文件
  2. nginx切割日志
  3. 040医疗项目-模块四:采购单模块—采购单创建好之后跳转到采购单修改页面(editcgd.action)
  4. mysql删除带有NULL的行
  5. 2016年6月27日 星期一 --出埃及记 Exodus 14:24
  6. GuessFist
  7. div容器内文本对齐--神奇的css
  8. plsql 把数据导出成为 .sql文件,记住了
  9. solr拼写检查代码逻辑
  10. P1137 旅行计划-----洛谷
  11. 系统启动 之 Linux系统启动概述(2)
  12. 关于微信小程序,一些想法
  13. Docker入门之--定制镜像
  14. STL算法设计理念 - 函数适配器
  15. python语法_模块_time_datetime_random
  16. LeetCode(65):有效数字
  17. [201804012]关于hugepages 3.txt
  18. Python学习笔记六:数据库操作
  19. rpgmakermv(6) YEP_ItemSynthesis.js物品合成插件
  20. 看完了红米5 Plus发布会,我觉得魅蓝Note6降价降多了

热门文章

  1. Nancy 自寄宿
  2. Linux发布WebApi
  3. [转] meta标签的作用及整理
  4. FORM表单中onclick()、submit()与onsubmit()的问题
  5. Maven+SpringMVC+SpringFox+Swagger整合示例
  6. 使用impala操作kudu之创建kudu表(内部表和外部表)
  7. BZOJ2119 股市的预测 字符串 SA ST表
  8. AtCoder Regular Contest 094 (ARC094) CDE题解
  9. netty03(基于4.1.23.Final 版本的案例)
  10. P2577 [ZJOI2005]午餐 状压DP