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
*/

 

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-24 12:26
点赞 评论 收藏
分享
门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
有没有佬投这个呀,怎么样呀求问
投递中科院空天信息创新研究院等公司10个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务