#2069. 园子里
园子里
园子里
题目描述
标题: 园子里 - Problem - QOJ.ac
#4532. 园子里
The problem was used in the following contests:
ns 在园子里过着快乐而充实的生活。突然有一天,从天而降 n 根柱子,这 n 根柱子在学堂路上排成一排,第 i 根柱子高度为 hi(即hi 为原始高度)米,然而,当有人站在第 i 根柱子上的时候,第 i 根柱子的高度会下降 ti(即当有人在上面时候 hi−ti 就是当前高度)米,离开之后又会恢复。ns 对这些柱子非常感兴趣,他可以从一根柱子跳到任意一个(包括他原本站着的柱子)原始高度不超过他所在柱子当前高度的柱子上,如果有多个柱子都满足,他会随机等概率地跳到一个满足条件的柱子上,如果没有柱子满足,他就会跳到地上。
ns 想知道,如果他从第 i 个柱子开始,期望跳多少次可以跳到地上。
输入格式
第一行一个整数 n,表示柱子的数量。
第二行 n 个空格隔开的整数 hi,表示每根柱子的高度(单位:米)。
第三行 n 个空格隔开的整数 ti,表示有人站在第 i 根柱子上的时候高度会下降 ti 米。
输出格式
输出一行 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
数据范围
输入格式见前文,输入的每个数都是整数,具体各测试点满足下列限制:
编号 n hi ti 特殊性 1 1≤n≤10 1≤hi≤105 0≤ti≤hi ti>0 2 无 3 1≤n≤102 ti>0 4 ti=0 5 ti=hi 6 无 7 8 9 1≤n≤103 ti>0 10 ti=0,hi全不相同 11 无 12 13 1≤n≤105 hi全部相同 14 ti>0 15 无 16 17 1≤n≤106 ti=hi 18 ti>0 19 无 20
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
4
4 2 2 3
2 1 1 2
2.000 1.000 1.000 1.000
样例 2
4
4 2 2 3
0 1 1 0
2.833 1.000 1.000 2.500