QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100

#3886. 厨房电缆混乱

Statistics

你开始了一个新项目:安装一套家庭自动化系统。你已经购买了所有组件,并在当地电子商店买到了一套包含多根不同长度线缆的促销套装。现在,你想把控制器与几米外的智能三明治机连接起来,但你缺少一根足够长的线缆。

为了解决这个问题,你必须将手中的一些线缆连接起来,形成一根长线。你测量了你拥有的每一根线缆的长度。每根线缆的两端都剥去了 5 厘米的绝缘层。连接两根线缆时,你需要将剥开的末端重叠并拧在一起。线缆末端只需接触即可(重叠长度为 0)。重叠长度不能超过 5 厘米,但重叠部分越长,连接质量越好。在两端——即控制器和三明治机处——你也各有 5 厘米的剥开末端,你必须以同样的方式将它们与你新制作的线缆连接起来。你链路的连接质量由所使用的最小重叠长度决定,你的目标是最大化这个值。

这个问题本来很简单,但你的完美主义室友讨厌不必要地使用线缆。因此,线缆必须形成一条直线,不能有任何环路或绕道。当然,剪断线缆是不可能的。

图 K.1:四根不同长度的线缆连接控制器和三明治机,重叠长度各不相同。连接 1 的重叠长度最大,连接 2 的重叠长度最小,其他连接介于两者之间。此设置的质量为 0。

考虑所有可能的线缆排列方式,找出质量最好的一种。

输入格式

输入包含: 一行包含两个整数 $n, g$ ($1 \le n \le 60, 11 \le g \le 1\,000$),表示线缆的数量以及控制器和三明治机外壳之间需要覆盖的距离(单位为厘米); $n$ 行,每行包含一个整数 $d$ ($11 \le d \le 1\,000$),表示线缆的长度(包括剥开的末端)。

每根线缆最多只能使用一次。

输出格式

输出一个数字,即能达到的最佳质量。该质量必须精确到相对误差或绝对误差(取较小者)不超过 $10^{-7}$。如果没有任何排列方式符合要求,则输出 impossible

样例

样例输入 1

3 70
20
35
50

样例输出 1

3.3333333

样例输入 2

3 150
20
35
50

样例输出 2

impossible

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.