AT_abc138_c [ABC138C] Alchemist

题目描述

你有一个锅和 $N$ 个食材。每个食材都有一个被称为“价值”的实数，第 $i$ 个食材的价值为 $v_i$。

将两个食材放入锅中后，这两个食材会消失，并生成一个新的食材。这个新食材的价值为原来两个食材的价值 $x, y$ 的平均值，即 $(x + y) / 2$。这个新食材也可以再次放入锅中进行合成。

经过 $N-1$ 次这样的合成后，最后只会剩下一个食材。请你求出最后剩下的这个食材的最大可能价值。

输入格式

输入通过标准输入给出，格式如下：

$N$ $v_1$ $v_2$ $\ldots$ $v_N$

输出格式

输出最后剩下的一个食材的最大可能价值，可以是小数或整数。

当你的输出与标准答案的绝对误差或相对误差不超过 $10^{-5}$ 时，将被判定为正确。

样例 1

输入

2
3 4

输出

3.5

样例 2

输入

3
500 300 200

输出

375

样例 3

输入

5
138 138 138 138 138

输出

138

说明/提示

限制条件

• $2 \leq N \leq 50$
• $1 \leq v_i \leq 1000$
• 输入中的所有值均为整数。

样例解释 1

如果最开始只有 $2$ 个食材，只能将它们一起放入锅中。价值为 $3, 4$ 的食材合成后，新食材的价值为 $(3 + 4) / 2 = 3.5$。另外，输出 3.50001、3.49999 等也会被判定为正确。

样例解释 2

这次最开始有 $3$ 个食材，第一次合成时可以选择放入锅中的食材。选择有以下 $3$ 种情况：

• 将价值为 $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 等也会被判定为正确。

由 ChatGPT 4.1 翻译