ICPC North America Qualifier Contest 2015 B. Bobby's Bet（概率计算）

Bobby and Betty have a bet. Betty bets Bobby that he cannot roll an SS-sided die (having values 11 through SS) and obtain a value \geq R≥R on at least XX out of YY rolls. Betty has a variety of dice with different numbers of sides SS, and all her dice are fair (for a given die, each side's outcome is equally likely). In order to observe statistically rare events while still giving Bobby a reason to bet, Betty offers to pay Bobby WWtimes his bet on each encounter. For example, suppose Betty bets Bobby 11 bitcoin that he can't roll at least a 55 on a 66-sided die at least two out of three times; if Bobby does, she would give him W = 3W=3 times his initial bet (\text{i.e.}i.e.she would give him 33 bitcoins). Should Bobby take the bet (is his expected return greater than his original bet)?

Input

Input begins with an integer 1\leq N\leq 10 0001≤N≤10000, representing the number of cases that follow. The next NN lines each contain five integers, RR, SS, XX, YY , and WW. Their limits are 1\leq R\leq S\leq 201≤R≤S≤20, 1\leq X\leq Y\leq 101≤X≤Y≤10, and 1\leq W\leq 1001≤W≤100.

Output

For each case, output "yes" if Bobby's expected return is greater than his bet, or "no" otherwise. Bobby is somewhat risk averse and does not bet if his expected return is equal to his bet.

输出时每行末尾的多余空格，不影响答案正确性

样例输入1复制

2
5 6 2 3 3
5 6 2 3 4

样例输出1复制

no
yes

样例输入2复制

3
2 2 9 10 100
1 2 10 10 1
1 2 10 10 2

样例输出2复制

yes
no
yes

题意：

甲掷一个S面的骰子，若甲能够在Y次以内掷出 >= X次面值 >= R，则甲获得W倍的赌注，甲不想冒险，判断甲的期望回报是否大于他的原赌注，如果大于，他会和乙打赌（yes），否则不打赌（no）。

思路：

掷一个S面的骰子，计算在Y次以内掷出 >= X次面值 >= R 的概率 p ，设甲的原赌注为1，则甲的期望回报就是 W * p，判断是否W * p > 1，是yes，不是no

（发现分母都是S ^ Y，进行了统一处理，一开始为了防爆，先除后乘的，竟然WA了，然后换成先乘后除就AC了…？？？

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 10;

ll c[12][12];

void init()
{
    c[0][0] = 1;
    for(int i = 1; i < 12; ++i)
    {
        c[i][0] = c[i][i] = 1;
        for(int j = 1; j < i; ++j)
        {
            c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
        }
    }
}

ll qpow(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1)
        {
            ans = ans * a;
        }
        a = a * a;
        b /= 2;
    }
    return ans;
}

int main()
{
    init();
    ll n, r, s, x, y, w;
    scanf("%lld", &n);
    while(n--)
    {
        scanf("%lld%lld%lld%lld%lld", &r, &s, &x, &y, &w);
        ll a = s - r + 1;
        ll b = r - 1;
        ll down = qpow(s, y);
        double p = 0;
        for(ll i = x; i <= y; ++i)
        {
            p += 1.0 * c[y][i] * qpow(a, i) * qpow(b, y - i) / down;
        }
        p = 1.0 * p * w;
        if(p > 1)
        {
            cout<<"yes"<<'\n';
        }
        else
        {
            cout<<"no"<<'\n';
        }
    }
    return 0;
}
/*
2
5 6 2 3 3
5 6 2 3 4
3
2 2 9 10 100
1 2 10 10 1
1 2 10 10 2
*/