题目描述

Cars! Where do they come from? Where do they go? Nobody knows. They appear where roads have been built, as if out of nowhere. Some say that no two cars are alike. Some say that if you look closely, you can see the pale ghosts of miserable humans inside them, trapped forever—particularly in the morning and late afternoon. What scientific eye could frame their fearful symmetry?

Well, yours, hopefully. As part of your government's Urban Traffic Control department, you are trying to write a paper on local traffic congestion. It is too dangerous to observe cars in the wild, of course, but you have been given some data on the traffic lights along your town's Main Street, and you would like to do some theoretical calculations about how well-synchronized they are.

Main Street is set out on a line, with traffic lights placed at various points along it. Each traffic light cycles between red and green with a fixed period, being red for $r$ seconds, then green for $g$ seconds, then red for $r$ seconds, and so on. The values of $r$ and $g$ may be different for different traffic lights. At time $0$, all the lights have just turned red.

Assume that an "ideal" car mystically appears at the west end of Main Street at a uniformly random real-valued time in the interval $[0, 2019!]$ (where $k!$ is the product of the first $k$ positive integers), driving eastwards at a slow crawl of $1$ meter/second until it hits a red light. What is the probability that it will make it through all the lights without being forced to stop? If it does hit a red light, which one is it likely to hit first?

Write a program to answer these questions.

输入格式

The first line of input contains an integer $n$ ($1 \leq n \leq 500$), the number of traffic lights. Each of the following $n$ lines contains three integers $x$, $r$, and $g$ describing a traffic light, where $x$ ($1 \leq x \leq 10^5$) is the position of the light along Main Street in meters, and $r$ and $g$ ($0 \leq r, g$ and $1 \leq r + g \leq 100$) are the durations in seconds of the red and green portions of the light's period (so the light is red from time $0$ to $r$, from time $r + g$ to $2r + g$, and so on).

The west end of Main Street is at position $0$, and the lights are listed in order of strictly increasing position.

输出格式

For each of the $n$ lights, output a line containing the probability that this light will be the first red light an "ideal" car hits. Then output a line containing the probability that an "ideal" car makes it all the way without stopping. Your answers should have an absolute error of at most $10^-6$.

题目大意

题目描述

Main 街坐落在一条东西向的直线上，上面有若干位置互异的红绿灯。每个红绿灯以某个固定周期在红绿之间循环。更具体地，它会先持续 $r$ 秒的红灯，再持续 $g$ 秒的绿灯，再持续 $r$ 秒的红灯...如此往复。对于不同的红绿灯，$r$ 和 $g$ 的值可能不同。在时刻 $0$，所有的红绿灯都恰好刚变为红灯。

假设此时有一辆“理想”汽车在前 $2019!$ 秒中的一个随机实数时刻神秘地出现在了 Main 街的最西端，向东以 $1~ \rm m/s$ 龟速行驶，直到遇到第一个红灯时停下，那么它有多大的概率通过所有红绿灯？如果它停下来了，那么它在每个红绿灯处停下的概率有多大？

输入格式

第一行一个整数 $n$（$1\le n\le 500$） 表示红绿灯的数量。

接下来每行三个整数 $x,r,g$（$1\le x \le 10^5$，$0\le r,g$ 且 $1\le r+g\le 100$）， 描述一个位置在从西往东 $x$ 米处的，红灯持续时间为 $r$，绿灯持续时间为 $g$ 的红绿灯。

最西侧即 $x=0$ 处，保证 $x$ 严格递增。

输出格式

前 $n$ 行第 $i$ 行每行输出一个实数表示在第 $i$ 个红绿灯停下的概率。

第 $n + 1$ 行输出一个实数表示通过所有红绿灯的概率。

你需要保证绝对误差不超过 $10^{-6}$.

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

提示

Source: ICPC 2019 World Finals.