← 返回题目列表

Codeforces · 1801/F

F. 另一个n维巧克力棒

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

Vasya 和他的朋友们想要切割一块巧克力,以获得至少 $$$k$$$ 块,而 Vasya 想要最大化其中最小的一块的体积。可以仅在小叶的交界处切割巧克力棒,并且每个切口必须沿着参与小叶形成的某个超平面穿过整个巧克力棒。只有在完成所有切割后,瓦西亚才将巧克力拆成碎片。

更正式地说,Vasya 想要选择数字 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le a_i$$$) - Vasya 将沿着每个维度将巧克力棒切割成的部分数量。必须满足条件 $$$b_1 \cdot b_2 \cdot \ldots \cdot b_n \ge k$$$ 才能在所有切割后获得至少 $$$k$$$ 块。可以注意到,使用这些参数进行最佳切割时,最小块将包含 $$$\lfloor \frac{a_1}{b_1} \rfloor \dotsm \lfloor \frac{a_n}{b_n} \rfloor$$$ 切片,其体积将等于 $$$\lfloor \frac{a_1}{b_1} \rfloor \dotsm \lfloor \frac{a_n}{b_n} \rfloor \cdot \frac{1}{a_1 a_2 \cdots a_n}$$$。

Vasya想要得到最小块的体积乘以$$$k$$$的最大可能值,即他想要最大化$$$\lfloor \frac{a_1}{b_1} \rfloor \dotsm \lfloor \frac{a_n}{b_n} \rfloor \cdot \frac{1}{a_1 a_2 \cdots a_n}\cdot k$$$。帮助他解决这个问题。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ $$$(1 \le n \le 100$$$, $$$1 \le k \le 10^7)$$$ — 巧克力棒的尺寸,以及需要分为多少部分。

第二行包含 $$$n$$$ 整数 $$$a_1,\ a_2,\ \dots,\ a_n$$$ $$$(1 \le a_i \le 10^7)$$$ — 沿每个维度放置巧克力的块数。

输出

打印一个数字——所获得的最小碎片的最大可能体积,乘以$$$k$$$,绝对或相对误差不超过$$$10^{-9}$$$。

如果在给定的限制下不可能将巧克力棒切成至少 $$$k$$$ 块,则输出 $$$0$$$。

示例

输入 #1

1 2
5

输出 #1

0.8

输入 #2

2 6
5 10

输出 #2

0.72

输入 #3

2 7
4 4

输出 #3

0.875

输入#4

2 3
4 5

输出#4

0.75

输入 #5

4 444
57 179 239 2

输出 #5

0.97557326850704739751

输入 #6

2 5
2 2

输出 #6

0

注意

在第一个示例中,一维巧克力棒可以划分如下:

那么答案将是 $$$\frac{2}{5} \cdot 2 = 0.8$$$

在第二个示例中,可以按如下方式切割巧克力块:

那么答案将是 $$$\frac{2}{5} \cdot \frac{3}{10} \cdot 6 = 0.72$$$

在第三个示例中,可以按如下方式切割巧克力块:

那么答案将是 $$$\frac{2}{4} \cdot \frac{1}{4} \cdot 7 = 0.875$$$