Description

儿童泳池是一个可以盛水的大容器，小孩子可以在里面玩耍。

你有 $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$ 度的水。你可以假设水只会因混合而改变温度，不会随时间加热或冷却。

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为三个用空格分隔的数：一个整数 $N$，两个实数 $V$ 和 $X$，含义如上所述。

接下来的 $N$ 行，每行包含两个用空格分隔的实数，分别为第 $i$ 个水源的出水速率 $R_i$ 和水温 $C_i$。体积以升为单位，流速以升每秒为单位，温度以摄氏度为单位。

所有实数均精确到小数点后四位。

Output Format

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

如果 $y$ 的绝对误差或相对误差在 $10^{-6}$ 以内，则视为正确。

6
1 10.0000 50.0000
0.2000 50.0000
2 30.0000 65.4321
0.0001 50.0000
100.0000 99.9000
2 5.0000 99.9000
30.0000 99.8999
20.0000 99.7000
2 0.0001 77.2831
0.0001 97.3911
0.0001 57.1751
2 100.0000 75.6127
70.0263 75.6127
27.0364 27.7990
4 5000.0000 75.0000
10.0000 30.0000
20.0000 50.0000
300.0000 95.0000
40.0000 2.0000

Case #1: 50.0000000
Case #2: 207221.843687375
Case #3: IMPOSSIBLE
Case #4: 0.500000000
Case #5: 1.428034895
Case #6: 18.975332068

Hint

样例解释

注意，第 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 翻译