UOJ Logo Universal Online Judge

UOJ

#161. 【清华集训2015】园子里

统计

ns 在园子里过着快乐而充实的生活。突然有一天,从天而降 $n$ 根柱子,这 $n$ 根柱子在学堂路上排成一排,第 $i$ 根柱子高度为 $h_i$(即$h_i$ 为原始高度)米,然而,当有人站在第 $i$ 根柱子上的时候,第 $i$ 根柱子的高度会下降 $t_i$(即当有人在上面时候 $h_i-t_i$ 就是当前高度)米,离开之后又会恢复。ns 对这些柱子非常感兴趣,他可以从一根柱子跳到任意一个(包括他原本站着的柱子)原始高度不超过他所在柱子当前高度的柱子上,如果有多个柱子都满足,他会随机等概率地跳到一个满足条件的柱子上,如果没有柱子满足,他就会跳到地上。

ns 想知道,如果他从第 $i$ 个柱子开始,期望跳多少次可以跳到地上。

输入格式

第一行一个整数 $n$,表示柱子的数量。

第二行 $n$ 个空格隔开的整数 $h_i$,表示每根柱子的高度(单位:米)。

第三行 $n$ 个空格隔开的整数 $t_i$,表示有人站在第 $i$ 根柱子上的时候高度会下降 $t_i$ 米。

输出格式

输出一行 $n$ 个浮点数,每两个浮点数用一个空格隔开,第 $i$ 个数表示ns从第 $i$ 根柱子开始,期望跳多少步可以跳到地上,如果期望步数为无穷,输出 $0$ ;如果你输出的每个浮点数与标准答案的误差(此处误差定义为你的答案与标准答案差的绝对值)均不超过 $0.001$ ,你的答案将被视为正确。

注意,我们会用一个特殊的程序来判断你的答案正确与否,你输出每个浮点数的字符串长度应该不超过 $20$ 。

定义无穷可以参与运算,无穷+X=无穷,无穷-X=无穷,无穷*X=无穷,无穷/X=无穷(X为任一实数,在除法中不为0)

样例一

输入

4
4 2 2 3
2 1 1 2

输出

2.000 1.000 1.000 1.000

样例二

输入

4
4 2 2 3
0 1 1 0

输出

2.833 1.000 1.000 2.500

样例三

输入

4
4 2 2 3
0 0 0 0

输出

0 0 0 0

数据范围

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$

输入格式见前文,输入的每个数都是整数,具体各测试点满足下列限制:

编号 $n$ $h_i$ $t_i$ 特殊性
$1$ $1 \leq n \leq 10$ $1 \leq h_i \leq 10^5$ $0 \leq t_i \leq h_i$ $t_i>0$
$2$
$3$ $1 \leq n \leq 10^2$ $t_i>0$
$4$ $t_i=0$
$5$ $t_i=h_i$
$6$
$7$
$8$
$9$ $1 \leq n \leq 10^3$ $t_i>0$
$10$ $t_i=0$,$h_i$全不相同
$11$
$12$
$13$ $1 \leq n \leq 10^5$ $h_i$全部相同
$14$ $t_i>0$
$15$
$16$
$17$ $1 \leq n \leq 10^6$ $t_i=h_i$
$18$ $t_i>0$
$19$
$20$

下载

样例下载