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 自动生成**