#P2536. [Neerc2008]Clock

    ID: 1588 传统题 800ms 256MiB 尝试: 6 已通过: 1 难度: 9 上传者: 标签>CF2600省选/NOI-线性 DPSlope Trick绝对值分段线性化向下取整与向上取整

[Neerc2008]Clock

题目描述

一位著名的俄罗斯建筑师计划建造一座巨型时钟,用来表示从宇宙诞生开始经过的时间。

这个时钟有 nn 根指针,每根指针都以恒定的角速度旋转。按照转动速度从快到慢,依次将它们编号为 1,2,…,n1,2,\ldots,n。

  • 第 11 根指针最快,每 6060 秒转一圈。
  • 对于 1≤i<n1\le i<n,当第 ii 根指针转动 did_i 圈时,第 i+1i+1 根指针恰好转动 11 圈。

调整时钟的方法如下:你可以抓住某根指针末端的把手,将这根指针沿顺时针或逆时针方向任意旋转。与此同时:

  • 所有转速比它慢的指针,会按照各自正常角速度之间的比例随之转动;
  • 所有转速比它快的指针不会移动。

由于每根指针都非常巨大,调整时钟是一项费力的工作。一次操作的代价,是抓住的那根指针末端把手沿圆弧走过的距离;整个调整过程的总代价,是所有操作的代价之和。

例如,一个时钟有秒针、分针、时针三根指针,长度分别为 55、1515、1010 米。现在要把时钟从 2:30 调整到 6:00。一种最优操作方法是:

  1. 将分针顺时针旋转 180∘180^\circ,此时较慢的时针会随之转动;
  2. 再将时针顺时针旋转 90∘90^\circ。

总共移动把手的距离为

$$15\times\pi+10\times\frac{\pi}{2}=20\pi\approx62.83185\text{ 米}。$$

图 1:原题配图。左图为初始时刻,中图为调整分针的过程,右图为继续调整时针直至目标时刻。

给定时钟的结构、各指针长度、时钟当前显示的时间和需要调整到的真实时间,求使时钟显示正确所需的最小把手移动总距离。

输入格式

第一行包含一个整数 nn,表示指针的数量(1≤n≤501\le n\le50)。

第二行包含 n−1n-1 个整数 d1,d2,…,dn−1d_1,d_2,\ldots,d_{n-1}(2≤di≤1062\le d_i\le10^6)。当 n=1n=1 时,这一行没有数字。

第三行包含 nn 个整数 l1,l2,…,lnl_1,l_2,\ldots,l_n,表示各根指针的长度(1≤li≤1061\le l_i\le10^6)。

接下来两行,每行包含一个非负整数:

  • 第一行表示时钟当前显示的时间 t1t_1;
  • 第二行表示需要调整到的真实时间 t2t_2。

时间单位均为秒,从宇宙诞生时起计算,满足 0≤t1,t2<2630\le t_1,t_2<2^{63}。

输出格式

输出一个实数,表示最小把手移动总距离。

结果至少应精确到小数点后 44 位。评测使用浮点数比较,允许绝对误差不超过 1.1×10−41.1\times 10^{-4}(与原始数据包中的官方比较器一致)。建议输出至少 1010 位小数。

输入输出样例 #1

输入 #1

3
60 12
5 15 10
52200
453600

输出 #1

62.831853072

样例说明

三根指针每转一圈分别需要 6060 秒、36003600 秒和 4320043200 秒。虽然给出的时间是从宇宙诞生开始累计的秒数,但钟面显示的状态只与各指针旋转的整圈余数有关。

本样例的最优操作与图 1 一致,最短距离为 20π20\pi。