HDu 4465 Candy(2012 ACM-ICPC成都ライブ)
1784 ワード
単純確率問題は,残りのn個から残りの0個に直接プッシュできる.現在、残りのx個の確率が(1−p)のcandyである場合、確率はC(2*n−x,x)*pow(p,n+1)*pow(1−p,n−x)である.
x−1を書く場合,組合せ数は直接プッシュできることが分かったので,直接求めることができる.しかし、pが小さいかもしれないし、nが大きいかもしれないことを考慮すると、pow関数を直接使うと精度が失われ、doubleタイプをlog 10の形式に書くことができ、精度を保存することができます.
x−1を書く場合,組合せ数は直接プッシュできることが分かったので,直接求めることができる.しかし、pが小さいかもしれないし、nが大きいかもしれないことを考慮すると、pow関数を直接使うと精度が失われ、doubleタイプをlog 10の形式に書くことができ、精度を保存することができます.
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<fstream>
#include<sstream>
#include<bitset>
#include<vector>
#include<string>
#include<cstdio>
#include<cmath>
#include<stack>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define FF(i, a, b) for(int i=a; i<b; i++)
#define FD(i, a, b) for(int i=a; i>=b; i--)
#define REP(i, n) for(int i=0; i<n; i++)
#define CLR(a, b) memset(a, b, sizeof(a))
#define debug puts("**debug**")
#define LL long long
#define PB push_back
#define SL(a) strlen(a)
using namespace std;
const int N = 11;
const int MOD = 1e9 + 7;
int main()
{
int n, cas = 1, i, j;
double p, ans, now;
while(scanf("%d%lf", &n, &p) != EOF)
{
now = log10(p) * (n + 1);
ans = pow(10.0, now) * n;
for(i = n - 1; i > 0; i --)
{
now = now + log10(2 * n - i + 0.0) - log10(n - i + 0.0) + log10(1 - p);
ans += pow(10.0, now) * i;
}
p = 1 - p;
now = log10(p) * (n + 1);
ans += pow(10.0, now) * n;
for(i = n - 1; i > 0; i --)
{
now = now + log10(2 * n - i + 0.0) - log10(n - i + 0.0) + log10(1 - p);
ans += pow(10.0, now) * i;
}
printf("Case %d: %.6lf
", cas ++, ans);
}
}