P13244 [GCJ 2014 Qualification] Cookie Clicker Alpha

Cookie Clicker 是 Orteil 开发的一款 Javascript 游戏，玩家通过点击一个巨大的曲奇图案来获得曲奇。点击巨型曲奇会获得曲奇，可以用这些曲奇购买建筑物，而这些建筑物又会帮助玩家获得更多曲奇。和本题一样，这款游戏非常专注于曲奇。不过本题只是借鉴了类似的思路，不要求你玩过 Cookie Clicker。请现在不要去玩这款游戏：否则你可能很久都回不来。 Cookie Clicker 由 Orteil 创作。Orteil 并未参与 Google Code Jam，也未对其进行背书。

在本题中，你一开始拥有 $0$ 个曲奇。你以每秒 $2$ 个曲奇的速度获得曲奇，方式是点击巨型曲奇。只要你拥有至少 $C$ 个曲奇，就可以购买一个曲奇农场。每次购买曲奇农场时，你需要花费 $C$ 个曲奇，并且你的曲奇产量每秒提升 $F$ 个曲奇。 一旦你拥有 $X$ 个未用于购买农场的曲奇，你就算获胜！请计算在最优策略下，你需要多长时间才能获胜。 假设 $C = 500.0$，$F = 4.0$，$X = 2000.0$。最优策略如下： 1. 你从 $0$ 个曲奇开始，产量为每秒 $2$ 个曲奇。 2. $250$ 秒后，你将拥有 $C = 500$ 个曲奇，可以购买一个产量为 $F = 4$ 曲奇/秒的农场。 3. 购买农场后，你的曲奇数变为 $0$，总产量变为每秒 $6$ 个曲奇。 4. 下一个农场需要 $500$ 个曲奇，你大约在 $83.3333333$ 秒后可以购买。 5. 购买第二个农场后，你的曲奇数归零，总产量变为每秒 $10$ 个曲奇。 6. 再买一个农场需要 $500$ 个曲奇，你在 $50$ 秒后可以购买。 7. 购买第三个农场后，你的曲奇数归零，总产量变为每秒 $14$ 个曲奇。 8. 再买一个农场仍需 $500$ 曲奇，但其实此时不买更优：直接等待直到拥有 $X = 2000$ 个曲奇，这需要大约 $142.8571429$ 秒。 总耗时：$250 + 83.3333333 + 50 + 142.8571429 = 526.1904762$ 秒。 注意你获得曲奇是连续的：比如游戏开始 $0.1$ 秒后你有 $0.2$ 个曲奇，$\pi$ 秒后你有 $2\pi$ 个曲奇。

输入的第一行包含一个整数 $T$，表示测试用例数量。接下来 $T$ 行，每行包含三个用空格分隔的实数：$C$、$F$ 和 $X$，含义如上文所述。 $C$、$F$ 和 $X$ 都至少有一位整数，后跟小数点和 $1$ 到 $5$ 位小数。不会有前导零。

对于每组测试用例，输出一行 "Case #$x$: $y$"，其中 $x$ 为测试用例编号（从 $1$ 开始），$y$ 为获得 $X$ 个美味曲奇所需的最短秒数。 建议将 $y$ 输出到 $7$ 位小数，但不是强制要求。如果 $y$ 的绝对误差或相对误差在 $10^{-6}$ 以内，则视为正确。

**数据范围** - $1 \leq T \leq 100$。 **小数据集（8 分）** - 时间限制：~~60~~ 3 秒。 - $1 \leq C \leq 500$。 - $1 \leq F \leq 4$。 - $1 \leq X \leq 2000$。 **大数据集（11 分）** - 时间限制：~~120~~ 5 秒。 - $1 \leq C \leq 10000$。 - $1 \leq F \leq 100$。 - $1 \leq X \leq 100000$。 翻译由 GPT4.1 完成。