#6587. 「ICPC World Finals 2019」交通堵塞

内存限制:1024 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: HeRaNO

题目描述

车!它们从哪里来?它们要到哪里去?没人知道。它们出现在已建成的道路上,好像无处不在。一些人说没有两辆车是一样的。一些人说如果你仔细观察,你能看到它们里面有着被永远困住,处境悲惨的人的苍白灵魂——尤其是在早晨和傍晚。是怎样科学的眼光才能定格这样恐怖的对称性。

万幸的是,是你的眼光。作为城市交通管理局的一份子,你正尽力写一篇关于当地交通堵塞的论文。当然,实地观察车辆是危险的。但是现在提供给你你镇主路上的一些交通信号灯的数据,你想要进行一些理论计算去确定他们同步得有多好。

主路可以看成一条直线,交通信号灯沿街放在两两不同点上。每个交通灯按一个固定周期亮绿灯和红灯,红灯亮 r 秒,绿灯亮 g 秒,然后红灯亮 r 秒,以此类推。不同交通信号灯 r g 的值可能不同。在 0 时刻,所有的信号灯都恰好变为红色。

假设在时刻 k ,一辆「理想的」车神秘地出现在主路最西侧, k 是一个在 [0,2019!] 范围内均匀随机的实数值(此处 k! 是前 k 个正整数之积)。这辆车以每秒 1 米的龟速向东行驶,直到遇到红灯才停下来。请问在没有遇到红灯的情况下通过主路的概率有多大?如果遇到了红灯,哪一个红灯是最有可能第一个遇到的?

请写一个程序回答这些问题。

输入格式

第一行包含一个正整数 n ,表示交通信号灯的数量。

接下来 n 行,每行三个正整数 x,r,g x 表示这个交通信号灯在主路上的位置,以米为单位。 r,g 是红灯和绿灯的持续时间,以秒为单位(所以红灯亮的时间是从 0 时刻到 r 时刻,从 r+g 时刻到 2r+g 时刻,以此类推)。

主路的最西端坐标是 0 ,这些交通信号灯按照坐标严格递增的顺序给出。

输出格式

输出 n+1 行,对于前 n 行,第 i 行输出这辆「理想的」车在第 i 个交通信号灯首次遇到红灯停下的概率,最后一行输出这辆车没有遇到红灯的情况下通过主路的概率。你的答案与标准答案的绝对误差不能大于 10^{-6}

样例

样例输入 1

4
1 2 3
6 2 3
10 2 3
16 3 4

样例输出 1

0.4
0
0.2
0.171428571429
0.228571428571

样例输入 2

6
4 1 5
9 8 7
13 3 5
21 5 7
30 9 1
2019 20 0

样例输出 2

0.166666666667
0.466666666667
0.150000000000
0.108333333333
0.091666666667
0.016666666667
0.000000000000

数据范围与提示

对于全部数据, 1\le n\le 500,1\le x\le 10^5,r,g\ge 0,1\le r+g\le 100