🥣 牛局长的“分汤”实验

（兔猫信奥学院 · 牛局长 × 闪电 × 豹警官 × 朱迪 × 尼克）

故事背景

今天的概率论课堂，牛局长 端来两大桶相同容量的汤：A 型与 B 型，各 $n$ 毫升。 每个志愿者随机从四种等概率操作中选一种盛汤：

操作	A 汤 (ml)	B 汤 (ml)
①	100	0
②	75	25
③	50
④	25	75

若剩余汤量不足，则把能盛的全部盛完；当两桶都空时实验结束。

任务是求

$$\Pr\left(\text{A 先空}\right)+\tfrac12\Pr\left(\text{A、B 同时空}\right) $$

结果误差 ≤ $10^{-5}$ 视为正确。

---

题目描述

给定整数 $n;(0\le n\le10^{9})$：A、B 两桶的初始毫升数。 输出上述概率值。

---

输入格式

n

输出格式

probability

• 双精度浮点，推荐 printf("%.10f\n", ans)。

---

样例

输入	输出
50	0.62500
100	0.71875

---

算法说明

• 将单位缩小到 25 ml，设 m = ceil(n / 25)。

• 由于操作最大消耗 4 个单位，且当 n ≥ 4800 时答案逼近 1，可直接返回 1。

• 记忆化递归／DP：

  f(i,j) = ¼ Σ f(i-a[k], j-b[k])
  

  终止条件：

  • i≤0 < j → A 先空 ⇒ 1
  • i≤0 & j≤0 → 同时空 ⇒ ½
  • j≤0 < i → B 先空 ⇒ 0