F. Expected Earnings

你正在玩一个涉及红球和黑球袋子的游戏。最初，你被告知袋子里总共有 $n$ 个球。此外，你还被告知，袋子里恰好有 $i$ 个红球的概率为 $p_i / 10^6$。 你现在想要从这个袋子中购买球。你非常喜欢红色，因此每个红球价值 1 单位，而黑球没有价值。要购买一个球，如果袋中仍有球，你需要支付成本 $c$（其中 $0 ≤ c ≤ 1$），然后从袋中随机抽取一个球。你可以随时选择停止购买（甚至可以选择根本不购买）。 假设你以最优策略购买，以最大化期望利润（即：获得的红球数量减去购买所需的成本），请输出最大期望利润。 输入的第一行包含两个整数 $n, X$（$1 ≤ n ≤ 10 000$，$0 ≤ X ≤ 10^6$）。 接下来的一行包含 $n + 1$ 个整数 $p_0, p_1, \dots, p_n$（$0 ≤ p_i ≤ 10^6$）。 成本 $c$ 的值可以通过 $c = X / 10^6$ 计算得出。 请输出一个浮点数，表示最优期望值。 你的答案若绝对误差或相对误差不超过 $10^{-9}$，则会被接受。更具体地说，如果你的答案是 $a$，标准答案是 $b$，则当 $|a - b| \leq \max(10^{-9}, 10^{-9} \cdot |b|)$ 时，你的答案会被接受。 在此示例中，袋子包含 0、1、2、3 个红球的概率相等。此外，从袋中抽取一个球的成本为 0.2。 ## Input 输入的第一行包含两个整数 $n, X$（$1 ≤ n ≤ 10 000$，$0 ≤ X ≤ 10^6$）。输入的下一行包含 $n + 1$ 个整数 $p_0, p_1, \dots, p_n$（$0 ≤ p_i ≤ 10^6$）。成本 $c$ 的值可以通过 $c = X / 10^6$ 计算得出。 ## Output 请输出一个浮点数，表示最优期望值。你的答案若绝对误差或相对误差不超过 $10^{-9}$，则会被接受。更具体地说，如果你的答案是 $a$，标准答案是 $b$，则当 $|a - b| \leq \max(10^{-9}, 10^{-9} \cdot |b|)$ 时，你的答案会被接受。 [samples] ## Note 在此示例中，袋子包含 0、1、2、3 个红球的概率相等。此外，从袋中抽取一个球的成本为 0.2。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the total number of balls in the bag. Let $ p_i \in \mathbb{R} $ for $ i \in \{0, 1, \dots, n\} $ denote the unnormalized probability that the bag contains exactly $ i $ red balls. Let $ c = \frac{X}{10^6} \in [0, 1] $ be the cost per draw. Let $ R $ be a random variable representing the number of red balls in the bag, with probability mass function: $$ \mathbb{P}(R = i) = \frac{p_i}{\sum_{j=0}^n p_j}, \quad i = 0, 1, \dots, n. $$ **Constraints** 1. $ 1 \leq n \leq 10{,}000 $ 2. $ 0 \leq X \leq 10^6 $ 3. $ 0 \leq p_i \leq 10^6 $ for all $ i \in \{0, 1, \dots, n\} $ 4. $ \sum_{i=0}^n p_i > 0 $ **Objective** Compute the maximum expected profit $ V^* $, defined as: $$ V^* = \sup_{\tau} \mathbb{E}\left[ \text{number of red balls drawn} - c \cdot \tau \right], $$ where $ \tau $ is a stopping time (number of draws made), and at each step, a ball is drawn uniformly at random from the remaining balls, with the composition of the bag unknown but governed by the prior distribution over $ R $. The optimal strategy is determined by dynamic programming over the state $ (r, b) $, where $ r $ is the expected number of red balls remaining and $ b $ is the expected number of black balls remaining, updated via Bayes’ rule after each draw. However, due to symmetry and linearity of expectation under the given prior, the problem reduces to computing the value function $ V(k) $ for $ k = 0, 1, \dots, n $, where $ V(k) $ is the maximum expected profit when $ k $ balls remain in the bag, under the posterior distribution of red balls given the history. Let $ \mu_k = \mathbb{E}[R \mid \text{history after } n-k \text{ draws}] $ be the expected number of red balls remaining when $ k $ balls are left. Then the recurrence is: $$ V(0) = 0 $$ $$ V(k) = \max\left( 0,\ \frac{\mu_k}{k} - c + \mathbb{E}[V(k-1) \mid \text{draw}] \right) $$ But since the prior is over the *initial* number of red balls, and draws are without replacement, the optimal value is computed via: Let $ \pi_i = \frac{p_i}{\sum_{j=0}^n p_j} $ be the normalized prior. Define $ f(k, r) $ as the maximum expected profit when $ k $ balls remain and exactly $ r $ of them are red. But $ r $ is unknown. Instead, define $ V(k) $ as the maximum expected profit starting with $ k $ balls remaining, under the current posterior distribution over the number of red balls. Let $ \mathbb{E}_k[R] $ denote the expected number of red balls among the remaining $ k $ balls, given the prior and the history of $ n-k $ draws. But since we have no information from draws until we make them, and we must compute the optimal strategy *before* any draws, we use the following known result for such Bayesian optimal stopping problems: Let $ \mu = \mathbb{E}[R] = \sum_{i=0}^n i \cdot \pi_i $. At each step, if $ k $ balls remain, the probability that the next ball drawn is red is $ \frac{\mathbb{E}_k[R]}{k} $. But under the symmetric prior and uniform random draw, the posterior expectation of red balls remaining after $ t $ draws is linear and can be computed via the law of total expectation. It is known that in such problems with a symmetric prior and uniform draws, the optimal expected value satisfies: $$ V(k) = \max\left( 0,\ \frac{\mu_k}{k} - c + \left( \frac{\mu_k}{k} \cdot V(k-1) + \left(1 - \frac{\mu_k}{k}\right) \cdot V(k-1) \right) \right) $$ Wait — this is incorrect. The expectation does not collapse that way. Actually, the correct recurrence is derived as follows: Let $ V(k) $ be the maximum expected profit when $ k $ balls remain, under the current posterior distribution over the number of red balls. Let $ \mu_k = \mathbb{E}[R_k] $, the expected number of red balls among the $ k $ remaining. Then, if we draw one ball: - With probability $ \frac{\mu_k}{k} $, we draw a red ball, gain $ +1 $, and move to state $ k-1 $ with expected red balls $ \mu_k - 1 $, so new expectation $ \mu_{k-1} = \mu_k - 1 $. - With probability $ 1 - \frac{\mu_k}{k} $, we draw a black ball, gain $ 0 $, and move to state $ k-1 $ with expected red balls $ \mu_k $, so $ \mu_{k-1} = \mu_k $. But this is not accurate: the posterior updates depend on the prior. Actually, under the initial prior $ \pi_i = \mathbb{P}(R = i) $, and given that we have drawn $ t $ balls without replacement, the posterior distribution over remaining red balls is updated via hypergeometric-like Bayesian updating. However, a key insight is that **the expected number of red balls among the remaining $ k $ balls is always $ \mu_k = \frac{k}{n} \cdot \mu $**, where $ \mu = \mathbb{E}[R] $, due to symmetry and exchangeability. This is true because all balls are exchangeable under the uniform random draw and symmetric prior: the probability any particular ball is red is $ \frac{\mu}{n} $, so the expected number among $ k $ remaining is $ k \cdot \frac{\mu}{n} $. Thus, at any state with $ k $ balls left, the probability the next ball is red is $ \frac{\mu_k}{k} = \frac{\mu}{n} $, a constant! Therefore, the value function satisfies: $$ V(k) = \max\left( 0,\ \frac{\mu}{n} - c + V(k-1) \right) $$ with $ V(0) = 0 $. Why? Because the expected gain from drawing one more ball is $ \frac{\mu}{n} $ (expected red balls gained), minus cost $ c $, and then we get $ V(k-1) $ from the remaining game. But this is **only** true if the posterior expectation of red balls per remaining ball is constant — which it is, due to exchangeability. Thus, the recurrence is: $$ V(0) = 0 $$ $$ V(k) = \max\left( 0,\ \frac{\mu}{n} - c + V(k-1) \right), \quad \text{for } k = 1, 2, \dots, n $$ where $ \mu = \sum_{i=0}^n i \cdot \pi_i = \frac{1}{\sum_{j=0}^n p_j} \sum_{i=0}^n i \cdot p_i $ Then the answer is $ V(n) $. **Final Formalization** **Definitions** Let $ \mu = \frac{\sum_{i=0}^n i \cdot p_i}{\sum_{i=0}^n p_i} $. Let $ c = \frac{X}{10^6} $. **Objective** Compute $ V(n) $, where: $$ V(0) = 0 $$ $$ V(k) = \max\left( 0,\ \frac{\mu}{n} - c + V(k-1) \right), \quad \text{for } k = 1, 2, \dots, n $$ Output $ V(n) $.