8306: BZOJ4306:玩具厂

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

在JIH考察的地图中有N个城市,被公路依次连成了一个环,JIH想在这些城市中建一个玩具厂。城市和公路都被编号为1..N,i号公路连接i-1号城市与i号城市(1号公路连接N号城市与1号城市),每个城市对玩具的需求为wi,每条公路的长度为di。当JIH在第i号城市建玩具厂时,JIH需要将玩具运输到其他城市(当然i城市除外)。设第i号城市到第j号城市的两条路径长度分别为l1、l2,则将玩具运输到第j号城市的费用为l1*l2*wj。总的运输费用为将玩具运到所有城市的运输费用的总和。 JIH当然想要总的运输费用最少,所以他会选最优的城市建玩具厂,如果有多个最优的城市,小月会等概率的选取其中一个建玩具厂。 由于JIH的调查工作没做好,只知道1..N-1号城市的wi,而N号城市的wi只知道它的取值范围[a,b],假设wi的值在实数区间[a,b]上的概率是均匀分布的。现在JIH只好去进行第二次调查,于是我们想知道每个城市建玩具厂的概率是多少。


输入格式

第一行有三个正整数N,a,b。 接下来N-1行每行一个正实数,为w[1]到w[N-1]。 接下来N行每行一个正实数,为d[1]到d[N]。


输出格式

N行,每行一个实数,表示在第i个城市建厂的概率


样例输入

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.75时,将在1或4号城市建玩具厂,当w[5]>18.75时,将在5号城市建玩具厂, 当w[5]=18.75时,将在1或4或5建玩具厂。 100%的数据中:N<=100000,a<=b<=10000,w[i]<=10000,d[i]<=10。 请不要提交,缺乏SPJ


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: