← 返回题目列表

Codeforces · 303/E

E. 随机排名

中文机器翻译题面 查看原题

想象一下有 n 名参与者的真实竞赛或考试。每个参与者都会获得特定的分数。如果我们对他们之前的表现进行一些统计,我们就可以或多或少地预测积分榜。

假设参与者的分数将均匀分布在区间 [li, ri] 中(分数可以是实数)。你能根据这些数据预测积分榜吗?换句话说,你应该为每个参与者说出他在记分牌上获得某个固定位置的概率。参与者按照记分牌中得分的增加进行排序。因此,得分最高的参与者获得最后的位置。

输入

第一行包含整数 n (1 ≤ n ≤ 80),显示我们有多少参与者。接下来的 n 行中的每一行都包含我们的预测,第 i 行包含一对整数 li, ri (0 ≤ li < ri ≤ 109) 作为参与者 i 的分布区间。

以某种方式考虑从 1 到 n 编号的参与者。

输出

输出n阶分布式矩阵a。矩阵的元素 aij 是参与者 i 具有等级 j 的概率。

如果您的答案最多有 10 - 6 个绝对或相对误差,则视为正确。

示例

输入 #1

2
1 6
4 9

输出 #1

0.9200000000 0.080
0.080 0.9200000000

输入 #2

8
0 2
1 3
2 4
3 5
4 6
5 7
6 8
7 9

输出 #2

0.875 0.125 0 0 0 0 0 0
0.125 0.750 0.125 0 0 0 0 0
0 0.125 0.750 0.125 0 0 0 0
0 0 0.125 0.750 0.125 0 0 0
0 0 0 0.125 0.750 0.125 0 0
0 0 0 0 0.125 0.750 0.125 0
0 0 0 0 0 0.125 0.750 0.125
0 0 0 0 0 0 0.125 0.875

注意

得分概率分布是连续的,这意味着,没有平局的可能性。