NC14734. 比赛
描述
你在打比赛，这场比赛总共有12个题
对于第i个题，你的队伍有a[i]的几率解决她
如果解决不了她呢？
由于所有人讨论的都很大声
所以你有b[i]的概率从左边那个队那里听会这个题的做法
有c[i]的概率从右边那个队那里听会这个题的做法
请问最终你们队伍解出0-12题的概率分别是多少
输入描述
第一行12个数表示a[1] -> a[12]
第二行12个数表示b[1] -> b[12]
第三行12个数表示c[1] -> c[12]
输出描述
输出13行，第i行表示解出i-1题的概率
保留6位小数
示例1
输入:
0.20 0.30 0.37 0.40 0.45 0.50 0.57 0.60 0.75 0.76 0.77 0.83 0.85 0.88 0.90 0.94 0.100 0.104 0.105 0.107 0.115 0.120 0.122 0.125 0.128 0.130 0.134 0.140 0.149 0.150 0.152 0.155 0.170 0.183 0.203 0.240
输出:
0.000000 0.000000 0.000000 0.000011 0.000160 0.001508 0.009620 0.041938 0.124153 0.243773 0.301960 0.212453 0.064424
C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 612K, 提交时间: 2020-05-18 19:09:56
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
double a[N],b[N],c[N],d[N],dp[N][13];
int main()
{
for(int i=1;i<=12;++i) cin>>a[i];
for(int i=1;i<=12;++i) cin>>b[i];
for(int i=1;i<=12;++i) cin>>c[i];
for(int i=1;i<=12;++i) d[i]=(1-a[i])*(1-b[i])*(1-c[i]);
dp[0][0]=1;
for(int i=1;i<=12;++i)
for(int j=0;j<=i;++j)
dp[i][j]=dp[i-1][j]*d[i]+dp[i-1][j-1]*(1-d[i]);
for(int i=0;i<13;++i)
printf("%.6lf\n",dp[12][i]);
}
Python3 解法, 执行用时: 70ms, 内存消耗: 4756K, 提交时间: 2022-10-25 14:38:00
n = 12
a = list(map(float, input().split()))
b = list(map(float, input().split()))
c = list(map(float, input().split()))
p = [a[i] + (1.0 - a[i]) * (b[i] + c[i] - b[i] * c[i]) for i in range(n)]
ans = [0.0] * (n + 1)
for i in range(1 << n):
x, y = 1.0, 0
for j in range(n):
if (i & (1 << j)) == 0: x *= (1.0 - p[j])
else: x *= p[j]; y += 1
ans[y] += x
for x in ans: print("{:.6f}".format(x))
C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 436K, 提交时间: 2023-05-17 21:49:32
#include<bits/stdc++.h>
using namespace std;
double a[12],b[12],c[12],x,d[13];
int i,j;
int main()
{
for(i=0;i<12;i++)scanf("%lf",a+i);
for(i=0;i<12;i++)scanf("%lf",b+i);
for(i=0;i<12;i++)scanf("%lf",c+i);
for(d[0]=1,i=0;i<12;i++)
{
x=(1-a[i])*(1-b[i])*(1-c[i]);
for(j=i+1;j;j--)d[j]=d[j-1]*(1-x)+d[j]*x;
d[j]*=x;
}
for(i=0;i<13;i++)printf("%.6lf\n",d[i]);
return 0;
}