#2069. 园子里

    ID: 2069 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest979来源:qoj.ac数据:公开样例动态规划

园子里

园子里

题目描述

标题: 园子里 - Problem - QOJ.ac

#4532. 园子里

Statistics

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