hdu 4870 Rating

hdu 4870 Rating

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

Rating

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 414    Accepted Submission(s): 261
Special Judge




Problem Description
A little girl loves programming competition very much. Recently, she has found a new kind of programming competition named “TopTopTopCoder”. Every user who has registered in “TopTopTopCoder” system will have a rating, and the initial value of rating equals to zero. After the user participates in the contest held by “TopTopTopCoder”, her/his rating will be updated depending on her/his rank. Supposing that her/his current rating is X, if her/his rank is between on 1-200 after contest, her/his rating will be min(X+50,1000). Her/His rating will be max(X-100,0) otherwise. To reach 1000 points as soon as possible, this little girl registered two accounts. She uses the account with less rating in each contest. The possibility of her rank between on 1 – 200 is P for every contest. Can you tell her how many contests she needs to participate in to make one of her account ratings reach 1000 points?

 


Input
There are several test cases. Each test case is a single line containing a float number P (0.3 <= P <= 1.0). The meaning of P is described above.
 


Output
You should output a float number for each test case, indicating the expected count of contest she needs to participate in. This problem is special judged. The relative error less than 1e-5 will be accepted.
 


Sample Input
   
   
1.000000 0.814700

 


Sample Output
   
   
39.000000 82.181160

 


Author
FZU
 


Source
 

题目:一个女孩打比赛,每次比赛结果若在前200名则能给她的rating加上50分,否则将会将去100分(rating最小为0,最大为1000—-可以进入前200的概率为p)。为了可以达到1000分。这个女孩使用两个帐号进行比赛,每次使用rating低的那个帐号比赛,直到有一个帐号rating达到1000。给定一个p。问最后须要进行比赛场数的期望值。

题解:首先我们想到的是推公式,以dp[i]代表从i*50-(i+1)*50的期望值。dp[0]和dp[1]须要单独处理。

            dp[0]代表我们从0-50须要进行的场数,分成两种情况:1.成功,概率为p,期望为1*p

                                                                                                              2.失败。概率1-p。期望为(1-p)*(1+dp[0])  

                                                                                                                —–所以dp[0]=1*p+(1-p)*(1+dp[0]) ,化简后dp[0]=1/p;

            dp[1]代表我们从50-100的场数期望,分成两种情况:1.成功,概率为p,期望为1*p

                                                                                                           2.失败,概率1-p,期望为(1-p)*(1+dp[0]+dp[1])   

                                                                                                                —–所以dp[1]=1*p+(1-p)*(1+dp[0]+dp[1]) ,化简后dp[1]=1+(1-p)/p*(1+dp[0]);

            i>2,dp[i]的求法,分成两种情况:1.成功,概率为p。期望为1*p

                                                                       2.失败,概率1-p,期望为(1-p)*(1+dp[i-2]+dp[i-1]+dp[i])   

                                                                        —–所以dp[i]=1*p+(1-p)*(1+dp[i-2]+dp[i-1]+dp[i])   。化简后dp[i]=1+(1-p)/p*(1+dp[i-2]+dp[i-1]);

这样,由于要使用两个帐号进行比赛,所以我们最后到达的状态就是一个帐号rating=1000,另外一个=950,仅仅须要进行dp求和即可了。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
    double p,q;
    double dp[20];
    while(cin>>p)
    {
        memset(dp,0,sizeof(dp));
        q=1.0-p;

        double sum=0;
        dp[0]=1.0/p;
        dp[1]=1.0+q/p*(1+dp[0]);
        sum+=(dp[0]+dp[1])*2;

        for(int i=2;i<=19;i++)
        {
            dp[i]=1.0+q/p*(1+dp[i-1]+dp[i-2]);
            sum+=dp[i]*2;
        }
        printf("%.6lf\n",sum-dp[19]);
    }
    return 0;
}

 高斯消元的做法(公式同上):

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const double eps=1e-11;  //设置为1e-9时Wa了
double a[40][40],x[40];
int equ,var;

void Debug()
{
    for(int i=0; i<equ; i++)
    {
        for(int j=0; j<=var; j++)
            printf("%4.2lf ",a[i][j]);
        puts("");
    }
    puts("");
}

double Gauss()
{
    int k,col,max_r;

    for(k=0,col=0; k<equ&&col<var; k++,col++)
    {
        max_r=k;
        for(int i=k+1; i<equ; i++)
            if(fabs(a[i][col])>fabs(a[max_r][col])) max_r=i;

        if(max_r!=k)
            for(int i=0; i<=var; i++)
            {
                swap(a[max_r][i],a[k][i]);
            }

        if(fabs(a[k][col])<eps)
        {
            k--;
            continue;
        }

        for(int i=k+1; i<equ; i++)
        {
            if(fabs(a[i][col])>eps)
            {
                double t=a[i][col]/a[k][col];
                for(int j=col; j<=var; j++)
                {
                    a[i][j]=a[i][j]-a[k][j]*t;
                }
            }
        }
    }

    //Debug();

    double ans=0;
    for(int j=var-1; j>=0; j--)
    {
        double temp=a[j][var];
        for(int r=j+1; r<var; r++)
            temp=(temp-a[j][r]*x[r]);

        x[j]=temp/a[j][j];
    }
    for(int j=0; j<var; j++)
        ans+=2.0*x[j];
    return ans-x[19];
}

void init(double p)
{
    equ=var=20;
    memset(a,0,sizeof(a));
    memset(x,0,sizeof(x));
    for(int i=0; i<20; i++)
    {
        a[i][var]=1.0;
    }
    a[0][0]=p;
    a[1][0]=p-1;
    a[1][1]=p;
    for(int i=2; i<=19; i++)
    {
        a[i][i]=p;
        a[i][i-1]=p-1;
        a[i][i-2]=p-1;
    }
    //Debug();
}

int main()
{
    double p;
    while(scanf("%lf",&p)!=EOF)
    {
        init(p);
        printf("%.6lf\n",Gauss());
    }
    return 0;
}

版权声明:本文博主原创文章,博客,未经同意不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116993.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 数据挖掘选择题_数据挖掘算法例题

    数据挖掘选择题_数据挖掘算法例题目录一、填空题二、计算题一、填空题❃随着信息技术的高速发展,数据库应用的规模、范围和深度不断扩大,网络环境成为主流等等。产生“数据丰富而信息贫乏”现象。❃“数据丰富而信息贫乏”现象导致大数据概念。❃数据(Data)、信息(Information)和知识(Knowledge)是广义数据表现的不同形式。❃大数据时代的数据挖掘技术需求分析的流派:数据论、方法论、环境论、特征论…

  • VirtualBox下安装ubuntu server 16.04

    VirtualBox下安装ubuntu server 16.04

    2021年10月28日
  • MATLAB中导入数据:importdata函数

    MATLAB中导入数据:importdata函数

  • c语言—数组详解(建议收藏)

    c语言—数组详解(建议收藏)文章目录一、一维数组1.一维数组的创建和初始化(1).数组的创建(2).数组的初始化2.一维数组的使用3.一维数组在内存中的存储二、二维数组1.二维数组的创建和初始化(1).二维数组的创建(2).二维数组的初始化2.二维数组的使用3.二维数组在内存中的存储三、数组作为函数参数1.一维数组2.二维数组四、数组指针和指针数组1.指针数组2.数组指针一、一维数组1.一维数组的创建和初始化(1).数组的创建数组是一组相同类型元素的集合。数组的创建方式:type_tarr_name[const

  • ON、WHERE、HAVING的差别

    ON、WHERE、HAVING的差别

    2021年12月14日
  • 【uboot】imx6ull uboot移植LAN8720A网卡驱动

    【uboot】imx6ull uboot移植LAN8720A网卡驱动文章目录相关文章1.前言2.IMX6ULLEthernetLAN8720A硬件连接3.支持LAN8720A修改步骤4.验证测试问题1:如何确定LAN8720A网卡PHYAD地址?问题2:如何确定devicetree中对resetgpio的定义?问题3:LAN8720A网卡nINTSEL是如何配置?问题4:IMX6ULLETH是如何被初始化的?相关文章1.《【uboot】imx6ulluboot2020.04源码下载和编译环境配置》2.《【Ethernet】以太网卡LAN8720

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号