0837. New 21 Game¶
题目信息¶
- 题号:
0837
- 难度:
Medium
- 主题:
概率、随机得分、停止条件
- 原题:
- 重点:
总分小于 k 时继续等概率抽取 1 至 maxPts,达到或超过 k 后立即停止;求最终总分不超过 n 的概率
题目重述¶
Alice 初始得分为 0。当当前总分严格小于 k 时,她会独立且等概率地从 1 到 maxPts 中抽取一个整数,并把它加入总分;一旦总分达到或超过 k,游戏立即停止,不再抽取。
请返回游戏结束时 Alice 总分不超过 n 的概率。若 k == 0,游戏从一开始就停止。答案与真实值的误差在 10^-5 以内即可接受。
0 <= k <= n <= 10^4,1 <= maxPts <= 10^4。
自建示例¶
部分终局超过上界:
输入:n = 2, k = 2, maxPts = 2
输出:0.75
解释:第一次抽到 2 的概率为 1/2,直接以总分 2 成功;第一次抽到 1 后,再抽到 1 的概率为 1/4,以总分 2 成功,抽到 2 则以总分 3 失败,因此成功概率为 1/2 + 1/4 = 0.75。
阈值为零时立即停止:
输入:n = 0, k = 0, maxPts = 7
输出:1.0
解释:k 达到允许的最小值 0,Alice 初始得分 0 已经不小于 k,因此不会抽取任何数字。最终得分 0 不超过 n = 0,成功概率为 1。