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

「ICPC World Finals 2019」交通堵塞

题目描述

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

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

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

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

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

输入格式

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

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

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

输出格式

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

样例 1

4
1 2 3
6 2 3
10 2 3
16 3 4
0.4
0
0.2
0.171428571429
0.228571428571
6
4 1 5
9 8 7
13 3 5
21 5 7
30 9 1
2019 20 0
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$。