AT_gigacode_2019_e.車の乗り継ぎ

Giga 大道是一条从西向东笔直延伸的道路，总长 $L$ 米。

E869120 君初始站在 Giga 大道的西端，驾驶一辆可以以每分钟 $V_S$ 米的速度行驶，且剩余行驶里程为 $D_S$ 米的汽车。

除此之外，这条道路上还有 $N$ 辆车。第 $i$ 辆车位于距离西端 $X_i$ 米处，可以以每分钟 $V_i$ 米的速度行驶，并且剩余行驶里程为 $D_i$ 米。

你想要驾驶车辆自西向东行驶，终点是 Giga 大道的东端。

在途中，你可以在车辆停下的地方选择其他车进行换乘，假设换乘时间不计。

那么，E869120 君是否能够到达 Giga 大道的东端？如果不能，请输出 impossible；如果能够，请输出到达东端所需的最短时间（以分钟为单位）。

无法到达 Giga 大道的东端时，请输出 impossible。
能够到达时，请输出所需的最短时间（以分钟为单位）。输出可以包含任意小数位，但答案与正确结果的绝对误差或相对误差必须不超过 $10^{-5}$，才能被视为正确。

约束条件

• $0 \leq N \leq 2\,019$
• $1 \leq L \leq 40\,075\,017$
• $1 \leq X_1, X_2, \dots, X_N \leq L-1$
• $X_1, X_2, \dots, X_N$ 互不相同
• $1 \leq V_S, V_1, V_2, \dots, V_N \leq 100\,000$
• $1 \leq D_S, D_1, D_2, \dots, D_N \leq L$

子任务

问题分为多个子任务，只有在代码通过该子任务的所有测试用例时才能视为完成该子任务。程序得分为完成的子任务分数之和。

1. (9 分) $N = 0$
2. (6 分) $N = 0$ 或 $N = 1$
3. (22 分) $N \leq 10$
4. (30 分) $V_S = 1$ 且对于所有的 $i$，$V_i = 1$
5. (33 分) 无额外约束

子任务 4 的提示

该子任务实质是判定问题，因为所有车辆的速度均为每分钟 1 米，所以如果能够到达东端，最短时间必然是 $L$ 分钟。思考这个提示有助于解决子任务 4。

示例解释

1. 通过以下行驶策略，你可以在 4 分钟内到达东端，这是最快的途径：

   • 先使用初始车辆行驶到 3 米处，用时 $3/1 = 3$ 分钟；
   • 接着换乘第一个车行驶到 6 米处，需要 $3/5 = 0.6$ 分钟；
   • 最后换乘第二个车行驶到东端的 10 米处，还需 $4/10 = 0.4$ 分钟；
   • 总用时为 $3 + 0.6 + 0.4 = 4$ 分钟。

2. 按照以下路线，只需 4.4 分钟即可到达终点：

   • 先用原车行驶到 3 米处，用 $3/1 = 3$ 分钟；
   • 然后直接换乘第一个车到达终点（10 米处），用 $7/5 = 1.4$ 分钟；
   • 总用时为 $3 + 1.4 = 4.4$ 分钟。

3. 这种情况下，无论如何都无法到达东端。并且，这个例子满足了子任务 4 的条件「$V_S = 1$，$V_i = 1$」。

4. 注意答案输出格式为 0.00001000090008，而不是 1.00009e-05。此外，例 4 满足子任务 1 的条件「$N = 0$」。

5. 此例中，在 50 米处换车是最佳选择。同时满足子任务 2 的条件「$N = 0$ 或 $N = 1$」。

6. 当绝对误差或相对误差不超过 $10^{-5}$ 时，46.861585 或 46.86159 的输出皆为正确答案。

本翻译由 AI 自动生成