← 返回题目列表

AtCoder · tenka1_2016_final_f

F. 盲目购买

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

配点 : 1500 点

問題文

Tenkaichi Toys 是一家以低价出售人偶而闻名的玩具店。这家店是 N 我们处理各种类型的图形,本期我们将它们作为图形进行介绍。 1,图 2,...,图 N 我们称之为。

商店 1 人偶在地板上单独出售。 i (1 ≦ i ≦ N) 是 您也可以写 1 個 P_i 你可以用日元购买。

商店 2 地板上有一个人物自动售货机。 G 如果输入日元,N 所有类型的数字都有相同的概率 1 碎片出现。这台机器自动产生数字,所以每个数字出现的概率总是 1/N 。

您访问了天下一玩具。你的目的就是这家商店 N 各种数字单独 至少获得 1 。商店的 1 地板和 2 您可以按任意顺序和任意次数使用楼层。此外,您可以花费的金额没有上限。如果我们采用一种策略来最小化支出金额的期望值,直到获得所有数据,那么期望值是多少?

制約

  • 2 ≦ N ≦ 36
  • 1 ≦ G ≦ 36
  • 1 ≦ P_i ≦ 36
  • 所有输入值都是整数。

入力

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

N G
P_1 P_2 ... P_N

出力

使用策略最小化消耗量的期望值直至获得所有数字时,输出消耗量的期望值。

输出与判断器的输出没有绝对或相对误差。 10^{-6} 如果答案如下,则视为正确。


入力例 1

2 4
5 6

出力例 1

9.5

如图 2 商店里有各种类型。 1 地板上的数字 1 该值应乘以 5 日元,数字 2 该值应乘以 6 你可以用日元购买。另外,店里的 2 在地板上的自动售货机里 4 如果插入一个圆圈,其中一个图形将以相同的概率出现。

这里最好的策略是首先从自动售货机购买人物模型。 1 购买一件商品并收到未售出的商品。 1 在地板上买。使用该策略时所花费的金额是,从自动售货机中出来的数字是 1 如果 4 + 6 = 10,图 2 如果 4 + 5 = 9 。因此,采用该策略的支出的预期值为 1/2 × 10 + 1/2 × 9 = 19/2 。无论你使用什么策略,这个期望值 它不能小于 19/2 。


入力例 2

3 10
5 6 7

出力例 2

18.0

由于自动售货机的定价较高,所有数字均为 1 最好在地板上购买。


入力例 3

3 1
5 6 7

出力例 3

5.5

由于自动售货机的定价较低,最好继续从自动售货机购买人物模型,直到所有人物模型都售完为止。


入力例 4

10 2
3 3 3 3 5 5 5 7 7 10

出力例 4

36.830952380952381