[PA 2021] Autostrada

特工 Karol 正在一条三车道的高速公路上驾驶他的红色汽车。在他前面有一些车，并且他们都在以一个取决于车道的固定速度向前行驶：第 $i$ 条车道的速度为 $v_i$ 且 $v_1 > v_2 > v_3$。其他车都不会变换车道和速度，但是 Karol 可以迅速变换车道，也可以迅速改变自己的车速到不超过 $v_0$ 的任意实数速度。他不能掉头，所以他的车的时速在区间 $[0, v_0]$ 中。 包括 Karol 在内，每辆车的长度都是 $1$。车之间可能会互相碰撞，但是 Karol 不能让这些车相撞。即：有正数长度的相交区间。形式化地，定义一辆车的位置为车头与高速路起点（即，Karol 的车刚开始的位置）之间的距离。相同车道的两辆车的位置差不能小于 $1$。 入口处有一段长为 $L$ 的公路，Karol 目前在第三车道的起点处。高速路无限延伸，并且在描述路段之外高速路上没有车。 请计算 Karol 最快多久后能超过所有车。换句话说，计算所有其他的车在最少多长时间后可以完全落后于 Karol 的车尾。 **注意：Karol 可能会在非整数时间内改变他的车道和速度，汽车的位置也可能是非整数的。** ## Input 第一行，五个整数 $L, v_0, v_1, v_2, v_3$； 接下来三行，其中第 $i$ 行有一个长为 $L$ 的字符串 $s_i$，描述第 $i$ 条车道，如果字符串 $s_i$ 的第 $j$ 个字符为 `#`，则表示那个位置有一辆车；如果为 `.`，则表示那个位置没有车。保证 $s_1$ 和 $s_2$ 的第一个字符都是 `.`，$s_3$ 的第一个字符为 `#`，表示 Karol 的车。输入中至少有两个 `#`。 ## Output 一行，一个实数，表示 Karol 超过所有车所用的最短时间。 与标准答案的绝对误差或相对误差在 $10^{-9}$ 之内的输出均可被接受。也就是说，你的答案为 $x$，如果标准答案是 $x_0$，若 $\frac{|x - x_0|}{\max(x_0, 1)} \leq 10^{-9}$ 则你的输出就会被判为正确。 [samples] ## Note 对于 $100\%$ 的数据，$2 \leq L \leq 2 \times 10^5$，$1 \leq v_3 < v_2 < v_1 < v_0 \leq 140$。