← 返回题目列表

AtCoder · typical90_bn

066. 各种阵列(★5)

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

配点: 5 点

問題文

数列爱好者高桥君制作了长度为 N 序列 使用 a 的序列。该序列通过从 a 可以得到第 i 第一个元素 a_i 的值为 独立于小于L_i 以上 R_i 下面 整数 中均匀随机选择决定。

这样得到的序列 a 的逆序数的期望值请计算。

另外,长度为 m 序列 使用 x 的“逆序数”指的是i < j 和 x_i > x_j 似乎是 (i, j) (1 \leq i, j \leq m) 的号码。

制約

  • 1 \leq N \leq 100
  • 1 \leq L_i \leq R_i \leq 100 (1 \leq i \leq N)
  • 所有输入均以整数形式给出

入力

输入是按以下格式从标准输入给出的。

N
L_1 R_1
\vdots
L_N R_N

出力

请输出答案。不过,相对误差或绝对误差为 10^{-7} 如果答案如下,则视为正确。


入力例 1

2
1 2
1 2

出力例 1

0.250000000000

数列 a 的可能有如下 4 是的。 请注意,我们正在寻找除以

  • a = (1, 1), 転倒数 0
  • a = (1, 2), 転倒数 0
  • a = (2, 1), 転倒数 1
  • a = (2, 2), 転倒数 0

因此,期望值是 \frac{1}{4} = 0.25 。 对于


入力例 2

3
3 3
1 1
4 4

出力例 2

1.000000000000

数列 a 是 a = (3, 1, 4) 唯一的,这个数列的逆序数是 1 。


入力例 3

10
1 10
38 40
8 87
2 9
75 100
45 50
89 92
27 77
23 88
62 81

出力例 3

13.696758921226