K点游戏

CMB22. K点游戏

描述

小招喵某日闲来无事，想验一下自己的人品，于是给自己定了一个游戏规则：

这个游戏有三个因素：N，K，W

游戏开始的时候小招喵有0点，之后如果发现自己手上的点不足K点，就随机从1到W的整数中抽取一个（包含1和W），抽到哪个数字的概率都是相同的。

重复上述过程，直到小招喵获得了K或者大于K点，就停止获取新的点，这时候小招喵手上的点小于等于N的概率是多少？

输入：N = 5， K = 1， W = 5

输出：1.00000

说明：开始有0点，不足1点，从[1,5]中随机取一个整数（一共5个数字，所以每个数字取到的概率都是1/5），获得后得分无论如何都大于了1点，停止，概率为1

输入：N = 6， K = 1， W = 10

输出：0.60000

说明：开始有0点，不足1点，从[1,10]中随机取一个整数（一共10个数字，所以每个数字取到的概率都是1/10），获得后有6/10的概率小于6点，且满足大于1点的条件，概率为0.6

输入描述

输入为3个整数，分别对应N，K，W，中间用空格隔开

其中0 <= K <= N <= 10000，1 <= W <= 10000

输出描述

输出为概率值，保留5位小数

示例1

输入:

21 17 10

输出:

0.73278

C 解法, 执行用时: 1ms, 内存消耗: 504KB, 提交时间: 2020-08-10

#include<stdio.h>
int main()
{
    int n,k,w;
    int i;
    scanf("%d %d %d",&n,&k,&w);
    double dp[k+w];
    double temp;
    for(i=k;i<=n;i++)
        dp[i]=1;
    for(i=n+1;i<k+w;i++)
        dp[i]=0;
    temp=((n-k+1)<w)?(n-k+1):w;
    for(i=k-1;i>=0;i--)
    {
        dp[i]=temp/w;
        temp+=dp[i]-dp[i+w];
    }
    printf("%.5f\n",dp[0]);
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 348KB, 提交时间: 2020-06-18

#include<stdio.h>

int main()
{
    int n,k,w;
    int i;
    scanf("%d %d %d",&n,&k,&w);
    double dp[k+w];
    double temp;
    for(i=k;i<=n;i++)
        dp[i]=1;
    for(i=n+1;i<k+w;i++)
        dp[i]=0;
    temp=((n-k+1)<w)?(n-k+1):w;
    for(i=k-1;i>=0;i--)
    {
        dp[i]=temp/w;
        temp+=dp[i]-dp[i+w];
    }
    printf("%.5f\n",dp[0]);
    return 0;
}