0808. Soup Servings¶
题目信息¶
- 题号:
0808
- 难度:
Medium
- 主题:
概率、随机过程、容量变化
- 原题:
- 重点:
四种供应方式等概率发生,直到至少一种汤为空;返回 A 先空的概率加上二者同时空概率的一半
题目重述¶
最初有 n 毫升 A 汤和 n 毫升 B 汤。每一轮从以下四种供应方式中等概率选择一种:
供应 100 毫升 A、0 毫升 B;
供应 75 毫升 A、25 毫升 B;
供应 50 毫升 A、50 毫升 B;
供应 25 毫升 A、75 毫升 B。
若某种汤剩余量不足本次需要供应的数量,就供应其全部剩余量。重复操作,直到 A 或 B 至少有一种为空。请返回“A 比 B 先空”的概率,加上“A 与 B 在同一轮同时为空”的概率的一半。答案与真实值的误差在 10^-5 以内即可接受。
0 <= n <= 10^9。
自建示例¶
部分分支需要继续供应:
输入:n = 75
输出:0.65625
解释:第一轮选择 (100,0) 或 (75,25) 时 A 先空,贡献均为 1;选择 (25,75) 时 B 先空,贡献为 0。选择 (50,50) 后两种汤各剩 25 毫升,下一轮的期望贡献为 (1 + 0.5 + 0.5 + 0.5) / 4 = 0.625。因此总概率为 (1 + 1 + 0.625 + 0) / 4 = 0.65625。
初始时两种汤都为空:
输入:n = 0
输出:0.5
解释:A 与 B 一开始同时为空,因此只计同时为空概率的一半。