怀化市网站建设_网站建设公司_阿里云_seo优化

题目描述

PDF

输入格式

输出格式

隐藏翻译

题意翻译

有 n 个人要去买东西，第 i 个人买到东西的概率为 pi​。现在已知恰好有 r 个人买了东西，在这种条件下，求每个人买到东西的概率。

本题有多组数据，满足测试数据组数不超过 50。

对于每组测试数据，共 n+1 行输入。第一行输入两个整数 n,r。第 2 到 n+1 行中第 i 行输入 pi−1​。输入以0 0结束。

输出格式：对于每组测试数据，输出 n+1 行。第一行先输出Case i，其中 i 为当前测试数据的编号。后面 n 行中第 i 行输出第 i 个人买到东西的概率，保留六位小数。

满足 1≤n≤20,0≤r≤n,0.1<pi​<1。

输入输出样例

输入 #1复制

3 2 0.10 0.20 0.30 5 1 0.10 0.10 0.10 0.10 0.10 0 0

输出 #1复制

Case 1: 0.413043 0.739130 0.847826 Case 2: 0.200000 0.200000 0.200000 0.200000 0.200000

代码实现：

#include<bits/stdc++.h> using namespace std; #define int long long int n, r, t, p[25]; double s, a[25], b[25]; void dfs(int x, int m, double f) { if (m > r) return; if (x > n) { if (m == r) { for (int i = 1; i <= m; i++)b[p[i]] += f; s += f; } return; } dfs(x + 1, m, f * (1 - a[x])); p[m + 1] = x; dfs(x + 1, m + 1, f * a[x]); } signed main() { while (cin>>n>>r) { if (n==0&&r==0)break; s = 0; for (int i = 1; i <= n; i++){cin>>a[i];b[i] = 0;} dfs(1, 0, 1); ++t; cout<<"Case "<<t<<":\n"; for (int i = 1; i <= n; i++)printf("%.6lf\n", 1.0 * b[i] / s); } return 0; }