题目描述

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}$ 以内，则认为正确。

3
2
200 100 100
3
10000 3000 4000 5000
5
3000 100 100 100 100 100

Case #1: 0.000000000000
Case #2: 0.088963394693
Case #3: -0.401790748826

提示

在样例 #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 完成