表示言語
/ /分数: 100 点
问题陈述
Lulu 发现了一个装有宝藏的魔法箱子。箱子上有 N 种不同的魔法,每种只施放一次,并且只能按正确顺序解除所有魔法才能打开。Lulu 是天才魔术师,已识别出箱子上的所有 N 魔法类型,但不知道必须解除它们的正确顺序。
为了打开盒子,露露尝试以下步骤。
-
露露从仍然施加在盒子上的法术中选择一个法术并尝试驱散它。 N 当露露尝试驱散第 i个法术时, M_i 魔力会被消耗。
-
如果尝试的法术在顺序上是正确的法术,驱散就会成功。如果顺序不正确,盒子会恢复到所有 N 法术都作用在其上的状态。露露可以立即知道驱散尝试是否成功。驱散法术所需的顺序不会改变。
-
一旦所有 N 法术被驱散,盒子就会打开。
鉴于 N 以及魔力消耗 M_i 每个法术,找出露露在使用最优策略打开盒子时预计消耗的魔力总量。正确的法术顺序是 N! 种可能顺序之一,且所有可能顺序的出现概率相等。
约束
- 1 \leq N \leq 100\,000
- 1 \leq M_i \leq 100\,000
- 所有给定的数字都是整数。
输入
输入由标准输入按以下格式给出:
N M_1 M_2 \dots M_N
输出
输出露露预计消耗的魔力总量。绝对误差或相对误差最多为 10^{-6} 已接受。
示例输入 1
1 10
示例输出 1
10
示例输入 2
2 10 20
示例输出 2
35
表示言語
/ /分数: 100 点
문제
루루는 보물이 담긴 마법의 상자를 발견했다. 상자에는 서로 다른 N가지의 마법이 한 번씩 걸려 있으며, 이를 정확한 순서대로 모두 해제해야만 상자를 열 수 있다. 천재 마법사인 루루는 상자에 걸려 있는 N가지 마법의 종류는 전부 알아냈지만 해제해야 할 올바른 순서는 알지 못한다.
루루는 상자를 열기 위해 아래와 같은 방법으로 상자 열기를 시도한다.
-
루루는 N가지 마법 중 아직 상자에 걸려 있는 마법 하나를 선택하여 해제를 시도한다. i번째 마법을 해제 시도할 때 M_i의 마력이 소모된다.
-
만약 해제 시도한 마법이 순서에 맞는 마법이라면 해제에 성공한다. 순서에 맞지 않는 마법이라면 N가지 마법이 모두 걸린 상태로 되돌아간다. 해제 시도가 성공했는지 바로 알 수 있다. 해제하는 데 필요한 마법의 순서는 바뀌지 않는다.
-
N개의 마법이 모두 해제되면 상자가 열린다.
N과 각 마법의 소모 마력 M_i가 주어질 때 루루가 최적의 전략으로 상자를 연다면 소모하게 될 마력 합의 기댓값을 구해 보자. 상자를 여는 올바른 마법의 순서는 N!가지 중 하나이며, 모든 가능한 순서가 올바른 순서일 확률은 동일하다.
제한
- 1 \leq N \leq 100\,000
- 1 \leq M_i \leq 100\,000
- 입력으로 주어지는 수는 모두 정수이다.
입력
입력은 다음 형식으로 표준 입력으로 주어진다.
N M_1 M_2 \dots M_N
출력
루루가 소모하게 될 마력 합의 기댓값을 출력한다. 절대/상대 오차는 10^{-6}까지 허용한다.
입력 예 1
1 10
출력 예 1
10
입력 예 2
2 10 20
출력 예 2
35