P16578 [GKS 2016 #A] Jane's Flower Shop

Jane 计划在当地的花卉市场开一家花店。初始成本包括摊位许可证、装修装饰、用于将鲜花从温室运送到商店的卡车等等。Jane 需要通过赚取收入来收回这些成本。她已经预估了接下来 $M$ 个月中每个月的净收入。 Jane 希望通过计算 $M$ 个月期间的 $IRR$（**内部收益率**）来预测她的花店会有多成功。给定一系列（时间，现金流）对 $(i, C_i)$，内部收益率是使得最后一月结束时总现金流恰好为 $0$ 的复合利率。IRR 越高，生意越成功。如果 IRR 低于通货膨胀率，那么一开始就不应该开店。 例如，假设初始成本为 $10,000$，花店运营 $3$ 个月，每个月的净收入分别为 $3,000$、$4,000$ 和 $5,000$。那么 IRR $r$ 由下式给出： $$-10000 \cdot (1 + r)^3 + 3000 \cdot (1 + r)^2 + 4000 \cdot (1 + r) + 5000 = 0$$ 在这种情况下，只有一个利率（约 $8.8963\%$）满足方程。 请帮助 Jane 计算她生意的 IRR。保证 $-1 < r < 1$，且每个测试用例中恰好只有一个解。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行是一个正整数 $M$：花店开业的月数。下一行包含 $M + 1$ 个非负整数 $C_i$（$0 \le i \le M$）。注意 $C_0$ 表示初始成本，其余所有 $C_i$ 均为利润。花店在每个月中总是获得正净利润或零净利润，永远不会出现负利润。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是一个浮点数：Jane 生意的 IRR。如果 $y$ 与正确答案的绝对误差或相对误差在 $10^{-6}$ 以内，则认为正确。

在样例 #1 中，IRR 为 $0$，Jane 刚好收回所有资金，没有利息。 样例 #2 和 #3 仅出现在大数据集中。 ### 限制条件 $1 \le T \le 100$。 $C_0 > 0$。 $0 \le C_i \le 1,000,000,000$。 **小数据集（测试集 1 – 可见）** $1 \le M \le 2$。 **大数据集（测试集 2 – 隐藏）** $1 \le M \le 100$。 翻译由 DeepSeek V4 Pro 完成