[code_festival_2018_qualb_d]Sushi Restaurant

ID: 3055

传统题

4000ms

1024MiB

尝试: 0

已通过: 0

难度: (无)

上传者:

admin

问题描述

CODE FESTIVAL 2018决赛有 $N$ 个参与者。现在，他们打算吃寿司作为晚餐。

每个参与者都有一个称为“饥饿度”的整数值。对于每个参与者，该值独立地确定如下：

以概率 $\frac{p_1}{q}$ 取饥饿度 $x_1$ ，以概率 $\frac{p_2}{q}$ 取饥饿度 $x_2$ ， … ，以概率 $\frac{p_M}{q}$ 取饥饿度 $x_M$ 。

你是一名寿司师傅。厨房里有 $N$ 个盘子，你要在每个盘子上放置一个或多个寿司。每个盘子上可以放置任意数量的寿司。

然后，这 $N$ 个盘子被送到参与者们坐的桌子上，他们各自拿一个盘子。当参与者拿走一个饥饿度为 $x$ 的参与者时，他的“不满度”为 $|x-y|$ ，其中 $y$ 是盘子上的寿司数量。

参与者们了解自己的饥饿度，并且他们会选择使所有人的不满度总和最小化的方式拿取盘子。这时，不满度总和称为“不适配度”。

你希望使不适配度的期望值最小。请计算在这种情况下不适配度的期望值。

约束条件

$N$ 是一个介于1到2000之间的整数。
$M$ 是一个介于1到2000之间的整数。
$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.6000000000

在这种情况下，只有一个参与者，他的饥饿度以概率 $\frac{30}{100} = 0.3$ 为1，以概率 $\frac{20}{100} = 0.2$ 为3，以概率 $\frac{50}{100} = 0.5$ 为9。

考虑在一个盘子上放置6个寿司。唯一的参与者拿走这个盘子，他的不适配度期望值，即参与者的不满度期望值，为$|1-6| \times 0.3 + |3-6| \times 0.2 + |9-6| \times 0.5 = 3.6$。

这是可以达到的最小值。

示例输入2

示例输出2

4.1600000000

在这种情况下，有两个参与者A和B，他们的饥饿度分布与示例输入1中的参与者相同。此外，假设有两个盘子，称为盘子1和盘子2。

在盘子1上放置9个寿司，在盘子2上放置1个寿司。例如，以 $\frac{30}{100} \times \frac{20}{100}$ 的概率，A和B的饥饿度分别为1和3。此时，由于A拿了盘子2，B拿了盘子1，两个人的不满度之和为 $|1-1| + |3-9| = 6$ ，这是最小化的情况，因此不适配度为6。

通过对其他情况进行类似的计算，我们可以得到，当寿司被安排在这种方式时，不适配度的期望值为4.16。