2111: [蓝桥杯2023初赛] 蜗牛

内存限制:512 MB 时间限制:2 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:176 通过:51

题目描述

这天,一只蜗牛来到了二维坐标系的原点。在 x 轴上长有 n 根竹竿。
它们平行于 y 轴,底部纵坐标为 0,横坐标分别为 x1, x2, ..., xn
竹竿的高度均为无限高,宽度可忽略。
蜗牛想要从原点走到第 n 个竹竿的底部也就是坐标 (xn, 0)。
它只能在 x 轴上或者竹竿上爬行,在 x 轴上爬行速度为 1 单位每秒;
由于受到引力影响,蜗牛在竹竿上向上和向下爬行的速度分别为 0.7 单位每秒和 1.3 单位每秒。
为了快速到达目的地,它施展了魔法,在第 i 和 i + 1 根竹竿之间建立了传送门(0 < i < n)。
如果蜗牛位于第 i 根竹竿的高度为 ai 的位置 (xi, ai),就可以瞬间到达第 i + 1 根竹竿的高度为 bi+1 的位置 (xi+1, bi+1)。
请计算蜗牛最少需要多少秒才能到达目的地。

输入格式

输入共 1 + n 行,第一行为一个正整数 n;
第二行为 n 个正整数 x1, x2, . . . , xn
后面 n − 1 行,每行两个正整数 ai, bi+1
对于 20% 的数据,保证 n ≤ 15;
对于 100% 的数据,保证 n ≤ 105,ai , bi ≤ 104,xi ≤ 109

输出格式

输出共一行,一个浮点数表示答案(四舍五入保留两位小数)。

输入样例 复制

3
1 10 11
1 1
2 1

输出样例 复制

4.20

数据范围与提示

蜗牛路线:
(0, 0) → (1, 0) → (1, 1) → (10, 1) → (10, 0) → (11, 0),花费时间为 1+1/0.7+0+1/1.3+1 ≈ 4.20