#P2703. 玩具厂

    ID: 1799 传统题 1000ms 128MiB 尝试: 56 已通过: 15 难度: 7 上传者: 标签>CF2300提高+/省选-一维前缀和绝对值分段线性化直线上包络单调栈

玩具厂

题目描述

有 NN 个城市,被公路依次连成了一个环,小月想在这些城市中建一个玩具厂。城市和公路都被编号为 1..N1..N,ii 号公路连接 i−1i-1 号城市与 ii 号城市(11 号公路连接 NN 号城市与 11 号城市),每个城市对玩具的需求为 wiw_i,每条公路的长度为 did_i。当我们在第 ii 号城市建玩具厂时,我们需要将玩具运输到其他城市(当然 ii 城市除外)。设第 ii 号城市到第 jj 号城市的两条路径长度分别为 l1l_1、l2l_2,则将玩具运输到第 jj 号城市的费用为 l1×l2×wjl_1 \times l_2 \times w_j。总的运输费用为将玩具运到所有城市的运输费用的总和。

小月当然想要总的运输费用最少,所以他会选最优的城市建玩具厂,如果有多个最优的城市,小月会等概率的选取其中一个建玩具厂。

由于小月的调查工作没做好,我们只知道 1..N−11..N-1 号城市的 wiw_i,而 NN 号城市的 wiw_i 我们只知道它的取值范围 [a,b][a,b],我们假设 wiw_i 的值在实数区间 [a,b][a,b] 上的概率是均匀分布的。

没办法,现在小月只好去进行第二次调查,于是我们想知道每个城市建玩具厂的概率是多少。

输入格式

第一行有三个正整数 NN,aa,bb。

接下来 N−1N-1 行,每行一个正实数,为 w[1]w[1] 到 w[N−1]w[N-1]。

接下来 NN 行,每行一个正实数,为 d[1]d[1] 到 d[N]d[N]。

输出格式

一共有 NN 行,每行一个实数,表示 11 到 NN 号城市建玩具厂的概率,保留 33 位小数。

输入样例

5 1 100
50
25
25
50
1
2
3
2
1

输出样例

0.090
0.000
0.000
0.090
0.821

提示

样例说明

当 w[5]<18.75w[5]<18.75 时,将在 11 或 44 号城市建玩具厂,当 w[5]>18.75w[5]>18.75 时,将在 55 号城市建玩具厂,当 w[5]=18.75w[5]=18.75 时,将在 11 或 44 或 55 建玩具厂。

数据规模和约定

30%30\% 的数据中:N≤1000N\le 1000。

30%30\% 的数据中:a=ba=b。

100%100\% 的数据中:N≤100000N\le 100000,a≤b≤10000a\le b\le 10000,w[i]≤10000w[i]\le 10000,d[i]≤10d[i]\le 10。