← 返回题目列表

AtCoder · icpc2016autumn_i

I. 多部门

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

问题陈述

我们正在开发世界上最酷的人工智能机器人产品。经过长期的努力,我们终于成功地将修订版 $R_{RC}$ 的产品作为候选版本发送给 QA 团队。 然而,他们报告说一些测试失败了! 因为我们懒得建立持续集成系统,所以我们不知道我们的软件何时损坏。我们只知道该软件通过了过去版本$R_{PASS}$的所有测试。 为了确定我们的软件开始出现故障的版本 $R_{ENBUG}$ ($R_{PASS} \lt R_{ENBUG} \le R_{RC}$),我们必须逐个版本地测试我们的产品。

这里,我们可以假设以下条件:

  • 当我们在修订版 $R$ 上进行测试时,如果 $R \lt R_{ENBUG}$ 则测试通过,否则测试失败。
  • 同样可能的是,$R_{PASS} + 1$ 和 $R_{RC}$ 之间的修订版是 $R_{ENBUG}$。

从第一个假设来看,我们不需要测试所有的修订。我们所要做的就是找到修订版 $R$,使得 $R - 1$ 处的测试通过,而 $R$ 处的测试失败。 我们有 $K$ 测试设备。使用它们,我们最多可以同时测试 $K$ 不同的修订版。我们称之为“parallel testing“。 由于测试环境的限制,即使我们没有使用所有$K$设备,在当前并行测试完成之前我们也无法开始新的测试。

并行测试需要一些成本。失败的测试越多,并行测试的成本就越高。 如果 $i$ 测试在并行测试中失败,则其成本为 $T_i$ ($0 \le i \le K$)。 如果我们多次运行并行测试,总成本就是它们的成本之和。

当然,我们希望通过仔细选择每次并行测试中要测试的修订数量和修订版本,来最小化确定 $R_{ENBUG}$ 的总成本。 如果我们采取最优策略,总成本的最小期望值是多少?


输入

输入由具有以下格式的单个测试用例组成。

$R_{PASS}$ $R_{RC}$ $K$
$T_0$ $T_1$ ... $T_K$

$R_{PASS}$ 和 $R_{RC}$ 是整数,分别表示测试通过和失败的软件版本号。 $1 \le R_{PASS} \lt R_{RC} \le 1{,}000$ 成立。 $K$ ($1 \le K \le 30$) 是我们可以在单个并行测试中测试的最大修订数量。 $T_i$ 是一个整数,表示 $i$ 测试失败的并行测试的成本 ($0 \le i \le K$)。 您可以假设 $1 \le T_0 \le T_1 \le \cdots \le T_K \le 100{,}000$。

输出

输出总成本的最小期望值。 输出不应包含大于 $0.0001$ 的错误。



示例输入 1

1 10 2
1 1 1

样本输入 1 的输出

2.0

示例输入 2

1 100 1
100 100

样本输入 2 的输出

670.7070707

示例输入 3

100 200 4
1 1 2 2 3

样本输入 3 的输出

4.6400000

示例输入 4

2 3 4
1 2 3 4 5

样本输入 4 的输出

0.0

示例输入 5

998 1000 4
10 100 1000 10000 100000

样本输入 5 的输出

55.0