Limak 是一只大北极熊。他为算法竞赛准备了n个问题。第 i 个问题的初始分数为 pi。另外,测试人员表示解决第 i 个问题需要 ti 分钟。问题不一定按难度排序,也许更难的问题初始分数较小,但现在改变它已经太晚了——Limak 已经宣布了问题的初始分数。尽管仍然可以调整丢分的速度,在本声明中用 c 表示。
让 T 表示解决所有问题所需的总分钟数(因此,T = t1 + t2 + ... + tn)。比赛将持续 T 分钟。所以它足以解决所有问题。
解决问题所给出的分数线性减少。在 x 分钟后解决第 i 个问题正好给出 $$p_i \cdot (1 - c \cdot \frac{x}{T})$$ 点,其中 $$c \in [0,1]$$ 是 Limak 必须选择的某个实常数。
假设 c 是固定的。在比赛期间,参与者选择他或她解决问题的顺序。有n个!可能的顺序,每个顺序都给出一些总点数,不一定是整数。如果给出的点数最多,我们就说该顺序是最优的。换句话说,该订单给出的总点数大于或等于任何其他订单给出的点数。显然,至少存在一个最优顺序。然而,可能存在不止一种最佳顺序。
Limak 假设每个参与者都会在一开始就正确估计 ti 并选择一些最佳顺序。他还假设测试人员正确预测了解决每个问题所需的时间。
对于两个不同的问题 i 和 j,使得 pi < pj Limak 不会高兴地看到参与者在问题 i 上获得的分数严格高于在问题 j 上获得的分数。他称这种情况为悖论。
不难证明,c = 0 时不会出现悖论。c 越大,情况可能会更糟。不可能存在悖论的最大实值 c(记住 $$c \in [0,1]$$)是多少,也就是说,对于解决问题的任何最优顺序都不存在悖论?
可以证明答案(所描述的最大c)总是存在。
输入
第一行包含一个整数 n (2 ≤ n ≤ 150 000) — 问题数。
第二行包含 n 个整数 p1, p2, ..., pn (1 ≤ pi ≤ 108) - 初始分数。
第三行包含 n 个整数 t1, t2, ..., tn (1 ≤ ti ≤ 108),其中 ti 是解决第 i 个问题所需的分钟数。
输出
在一行上打印一个实值 - $$c \in [0,1]$$ 中 c 的最大值,并且不存在存在悖论的最佳顺序。如果您的答案的绝对或相对误差不超过 10 - 6,则视为正确。
即:假设你的答案是a,陪审团的答案是b。如果 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$,检查程序将认为您的答案正确。
示例
输入 #1
3 4 3 10 1 1 8
输出 #1
0.62500000000
输入 #2
4 7 20 15 10 7 20 15 10
输出 #2
0.31901840491
输入 #3
2 10 20 10 1
输出 #3
1.00000000000
注意
在第一个示例中,存在 3 个问题。第一题为(4, 1)(初始分数为4,所需时间为1分钟),第二题为(3, 1),第三题为(10, 8)。总时间为 T = 1 + 1 + 8 = 10。
让我们证明 c = 0.7 存在一个悖论。按 1、2、3 的顺序解决问题可得出最佳总分,等于以下各项的总和:
1. 开始后 1 分钟解决: $$4 \cdot ( 1 - 0. 7 \cdot \frac { 1 } { 1 0 } ) = 3. 7 2$$
2.开始后2分钟解决:$$3 \cdot (1 - 0.7 \cdot \frac{2}{10}) = 2.58$$
3. 开始后 10 分钟解决: $$10 \cdot ( 1 - 0. 7 \cdot \frac { 1 0 } { 1 0 } ) = 3$$
因此,这个顺序总共给出 3.72 + 2.58 + 3 = 9.3 分,这是唯一的最佳顺序(您也可以计算其他 5 个可能顺序的总分,发现它们较低)。您应该检查问题 1 和 3 的要点以发现悖论。 4 < 10 但 3.72 > 3。事实证明,c = 0.625 不存在悖论,但任何更大的 c 都会存在悖论。
在第二个示例中,所有 24 个订单都是最优的。
在第三个示例中,即使 c = 1 也不存在悖论。