#P4306. 玩具厂

    ID: 3522 传统题 1000ms 128MiB 尝试: 38 已通过: 16 难度: 7 上传者: 标签>难度分类提高+/省选-排序与序列处理一维前缀和构造与建模绝对值分段线性化计算几何直线上包络单调栈CF2300

玩具厂

玩具厂

题目描述

NN 座城市沿公路连成一个环。第 ii 条公路长 did_i,连接第 i−1i-1 座和第 ii 座城市,其中第 11 条公路连接第 NN 座与第 11 座城市。

在城市 ii 建厂时,向另一座城市 jj 运送玩具的费用为 L1L2wjL_1L_2w_j,其中 L1,L2L_1,L_2 是沿环的两个方向从 ii 到 jj 的距离,wjw_j 是城市 jj 的需求。本市无需运输。总费用为运往所有其他城市的费用之和。

已知 w1,…,wN−1w_1,\ldots,w_{N-1},而 wNw_N 在实数区间 [a,b][a,b] 上均匀分布。若 a=ba=b,则 wN=aw_N=a。确定 wNw_N 后,挑选总费用最低的城市建厂。若多个城市并列最低,在这些城市中等概率选择。求每座城市最终被选中的概率。

输入格式

第一行是整数 NN 和两个正实数 a,ba,b。随后 N−1N-1 行,每行一个正实数,依次为 w1,…,wN−1w_1,\ldots,w_{N-1}。最后 NN 行,每行一个正实数,依次为 d1,…,dNd_1,\ldots,d_N。

输出格式

输出 NN 行。第 ii 行为在城市 ii 建厂的概率,样例保留三位小数。

样例 #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.75w_5<18.75 时,城市 11 和 44 并列最低。当 w5>18.75w_5>18.75 时,只有城市 55 最低。恰为 18.7518.75 时,三座城市并列最低。

数据规模与约定

1≤N≤1051\le N\le10^5,0<a≤b≤355000<a\le b\le35500,0≤wi≤1040\le w_i\le10^4,0<di≤10000<d_i\le1000。