玩具厂
题目描述
N 座城市沿公路连成一个环。第 i 条公路长 di,连接第 i−1 座和第 i 座城市,其中第 1 条公路连接第 N 座与第 1 座城市。
在城市 i 建厂时,向另一座城市 j 运送玩具的费用为 L1L2wj,其中 L1,L2 是沿环的两个方向从 i 到 j 的距离,wj 是城市 j 的需求。本市无需运输。总费用为运往所有其他城市的费用之和。
已知 w1,…,wN−1,而 wN 在实数区间 [a,b] 上均匀分布。若 a=b,则 wN=a。确定 wN 后,挑选总费用最低的城市建厂。若多个城市并列最低,在这些城市中等概率选择。求每座城市最终被选中的概率。
输入格式
第一行是整数 N 和两个正实数 a,b。随后 N−1 行,每行一个正实数,依次为 w1,…,wN−1。最后 N 行,每行一个正实数,依次为 d1,…,dN。
输出格式
输出 N 行。第 i 行为在城市 i 建厂的概率,样例保留三位小数。
样例 #1
样例输入 #1
5 1 100
50
25
25
50
1
2
3
2
1
样例输出 #1
0.090
0.000
0.000
0.090
0.821
样例说明
当 w5<18.75 时,城市 1 和 4 并列最低。当 w5>18.75 时,只有城市 5 最低。恰为 18.75 时,三座城市并列最低。
数据规模与约定
1≤N≤105,0<a≤b≤35500,0≤wi≤104,0<di≤1000。