Alchemist

题目描述

你有一个锅和 $N$ 个配料。每个配料有一个实数参数称为值，第 $i$ 个配料（$1 \leq i \leq N$）的值为 $v_i$。 当你把两个配料放入锅中，它们会消失并生成一个新的配料。新配料的值将是 $(x + y) / 2$，其中 $x$ 和 $y$ 是被消耗的配料的值，并且你可以再次将该配料放入锅中。 以这种方式组合配料 $N-1$ 次之后，你将只剩下一个配料。求这个配料可能达到的最大值。

输入格式

输入按以下格式从标准输入给出： $N$ $v_1$ $v_2$ $\ldots$ $v_N$

输出格式

输出一个十进制数（或整数），表示最后剩下的配料的最大可能值。 当你的输出与评测答案的绝对或相对误差不超过 $10^{-5}$ 时，将被判定为正确。

2
3 4

3.5

3
500 300 200

375

5
138 138 138 138 138

138

提示

$2 \leq N \leq 50$ $1 \leq v_i \leq 1000$ 输入中的所有值均为整数。如果你从两个配料开始，唯一的选择是把它们放入锅中。值为 $3$ 和 $4$ 的配料生成的配料值是 $(3 + 4) / 2 = 3.5$。 打印 $3.50001$、$3.49999$ 等也会被接受。
这次你从三个配料开始，你可以选择第一次组合使用哪两个。有三种可能的选择：

使用值为 $500$ 和 $300$ 的配料生成一个值为 $(500 + 300) / 2 = 400$ 的配料。下一次组合将使用此配料和值为 $200$ 的配料，结果为 $(400 + 200) / 2 = 300$。 使用值为 $500$ 和 $200$ 的配料生成一个值为 $(500 + 200) / 2 = 350$ 的配料。下一次组合将使用此配料和值为 $300$ 的配料，结果为 $(350 + 300) / 2 = 325$。 使用值为 $300$ 和 $200$ 的配料生成一个值为 $(300 + 200) / 2 = 250$ 的配料。下一次组合将使用此配料和值为 $500$ 的配料，结果为 $(250 + 500) / 2 = 375$。

因此，最后剩下的配料的最大可能值是 $375$。 打印 $375.0$ 等也会被接受。

标签: AtCoder|abc138C

来源

AtCoder|abc138C