配点: 700 点
問題文
CODE FESTIVAL 2018 决赛的参加者人数是 N 人。从现在开始,他们将在晚餐时吃寿司。
每位参加者 空腹度 拥有一个整数值。这个值对于每位参加者是独立的,如下所示确定。
- 確率 \frac{p_1}{q} 的饥饿度 x_1, 確率 \frac{p_2}{q} 的饥饿度 x_2, ... , 確率 \frac{p_M}{q} 的饥饿度 x_M.
你是一名寿司厨师。厨房里有 N 个盘子,你需要在每个盘子上放置至少 1 个寿司。盘子上可以放任意数量的寿司,每个盘子可以放不同数量的寿司。
然后,这些 N 个盘子被送到参加者们坐的桌子上,他们各自 1 拿取。
空腹度 x 的参与者拿了装有 y 个寿司的盘子时,该参与者的 不満度 是
您也可以写 |x - y| 。
参与者们能够掌握自己的饥饿度,并且他们会取盘子以使全体的不满度总和最小。此时全体的不满度总和称为 不適合度 。
你希望将寿司放在盘子上,使不适合度的期望值最小。请计算以这种方式将寿司放在盘子上时的不适合度的期望值。
制約
- N 是 您也可以写 1 以上 2 \ 000 的整数 给出了
- M 是 您也可以写 1 以上 2 \ 000 的整数 给出了
- 1 \leq x_1 < x_2 < x_3 < ... < x_M \leq 1 \ 000 \ 000.
- p_i \ (1 \leq i \leq M) 是, 1 以上 1 \ 000 \ 000 的整数 给出了
- q 是 您也可以写 1 以上 1 \ 000 \ 000 的整数 给出了
- p_1 + p_2 + p_3 + ... + p_M = q.
入力
输入将以以下形式从标准输入给出。
N M q x_1 p_1 x_2 p_2 x_3 p_3 : : x_M p_M
出力
输出不适合度期望值的可达最小值。
与评测答案的绝对误差或者相对误差 \pm 0.0001 以内则被视为正确。
入力例 1
1 3 100 1 30 3 20 9 50
出力例 1
3.6000000000
在这种情况下,参与者是 1 人,他的饥饿度为正确率 30/100 = 0.3 在 1, 確率 20/100 = 0.2 在 3, 確率 50/100 = 0.5 在 9 。
1 盘上 6 个寿司放在盘子上。唯一的参与者会拿走这个盘子,其不适合度的期望值,即该参与者的不满度的期望值为 |1-6| \times 0.3 + |3-6| \times 0.2 + |9-6| \times 0.5 = 3.6 。
这就是可以达到的最小值。共有
入力例 2
2 3 10 1 3 3 2 9 5
出力例 2
4.1600000000
在这种情况下,参与者是 2 人,我们称他们为 A 和 B。他们的饥饿度的正确分布与输入例 1 中参与者的相同。此外, 2 张盘子 1, 皿 2 。
考虑放置
皿 1 至
该值是 9 個, 皿 2 至
该值是 1 个寿司。
例如,确实率 30/100 × 20/100 下,A、B 的饥饿度分别 1, 3 是这样的。此时,由于 A 拿盘子 2,B 拿盘子 1 ,两人的不满度总和 |1-1| + |3-9| = 6 得到最小化,因此,不适合度为 6 。
对于其他情况也同样进行计算,就可以知道当寿司这样摆放时的不适合度的期望值为 4.16 。
这就是可以达到的最小值。共有
入力例 3
3 2 2 111111 1 999999 1
出力例 3
666665.9999999997
1 放在第几盘 111 \ 111 個, 2 放在第几盘 999 \ 999 個, 3 放在第几盘 555 \ 555 个寿司放置时,不适合度的期望值是 666 \ 666 ,这是可实现的最小值。