P13225 [GCJ 2015 #2] Kiddie Pool

儿童泳池是一个可以盛水的大容器，小孩子可以在里面玩耍。 你有 $N$ 个不同的水源可用。第 $i$ 个水源的出水速率为 $R_i$，水温为 $C_i$。最初，所有水源都是关闭的。每个水源只能被打开一次，也只能被关闭一次；打开或关闭水源的操作不需要额外时间。多个水源可以同时开启。 你的泳池可以容纳无限量的水，但你希望以最快的速度将泳池注满体积恰好为 $V$、温度恰好为 $X$ 的水。你可以最优地控制水源的开关（并非每个水源都必须使用），请问最少需要多少秒才能完成？ 在本题中，将体积为 $V_0$、温度为 $X_0$ 的水与体积为 $V_1$、温度为 $X_1$ 的水混合后，会瞬间得到体积为 $V_0+V_1$、温度为 $\frac{V_0 X_0 + V_1 X_1}{V_0 + V_1}$ 的水。例如，将 $5$ 升 $10$ 度的水与 $10$ 升 $40$ 度的水混合后，会得到 $15$ 升 $30$ 度的水。你可以假设水只会因混合而改变温度，不会随时间加热或冷却。

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为三个用空格分隔的数：一个整数 $N$，两个实数 $V$ 和 $X$，含义如上所述。 接下来的 $N$ 行，每行包含两个用空格分隔的实数，分别为第 $i$ 个水源的出水速率 $R_i$ 和水温 $C_i$。体积以升为单位，流速以升每秒为单位，温度以摄氏度为单位。 所有实数均精确到小数点后四位。

对于每个测试用例，输出一行，格式为 “Case #x: y”，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是将儿童泳池注满到指定体积和温度所需的最少秒数。如果无法实现，则 $y$ 应为字符串 IMPOSSIBLE。 如果 $y$ 的绝对误差或相对误差在 $10^{-6}$ 以内，则视为正确。

**样例解释** 注意，第 6 个样例不在 Small 数据集的范围内。 在第 1 个样例中，唯一的水源温度正好是目标温度。最优策略是立即打开它，直到注满 $10$ 升。由于每秒流出 $0.2$ 升，需要 $50$ 秒。 在第 2 个样例中，一种最优策略是先打开第一个水源，持续 $207221.843687375$ 秒，然后在结束前约 $0.092778156$ 秒打开第二个水源。 在第 3 个样例中，所有水源温度都低于目标温度，因此无法实现目标。 **数据范围** - $1 \leq T \leq 100$。 - $0.1 \leq X \leq 99.9$。 - $0.1 \leq C_i \leq 99.9$。 **小数据集（7 分）** - 时间限制：5 秒。 - $1 \leq N \leq 2$。 - $0.0001 \leq V \leq 100.0$。 - $0.0001 \leq R_i \leq 100.0$。 **大数据集（18 分）** - 时间限制：10 秒。 - $1 \leq N \leq 100$。 - $0.0001 \leq V \leq 10000.0$。 - $0.0001 \leq R_i \leq 10000.0$。 由 ChatGPT 4.1 翻译