E - Opening Magical Box Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

表示言語

/ /

Score : 100 points

Problem Statement

Lulu found a magical box containing treasure. The box has N distinct spells cast on it, one of each type, and it can be opened only by dispelling all of them in the correct order. Lulu, a genius magician, has identified all N types of spells on the box, but does not know the correct order in which they must be dispelled.

To open the box, Lulu attempts the following procedure.

  1. Lulu chooses one spell that is still cast on the box among the N spells and tries to dispel it. When Lulu tries to dispel the i-th spell, M_i magic power is consumed.

  2. If the attempted spell is the correct spell in the order, the dispelling succeeds. If it is not the correct spell in the order, the box returns to the state where all N spells are cast on it. Lulu can immediately tell whether the dispelling attempt succeeded. The order required for dispelling the spells does not change.

  3. Once all N spells are dispelled, the box opens.

Given N and the magic power cost M_i of each spell, find the expected total amount of magic power Lulu will consume if Lulu opens the box using an optimal strategy. The correct order of spells is one of the N! possible orders, and all possible orders are equally likely.

Constraints

  • 1 \leq N \leq 100\,000
  • 1 \leq M_i \leq 100\,000
  • All given numbers are integers.

Input

The input is given from Standard Input in the following format:

N
M_1 M_2 \dots M_N

Output

Output the expected total amount of magic power Lulu will consume. An absolute or relative error of at most 10^{-6} is accepted.

Sample Input 1

1
10

Sample Output 1

10

Sample Input 2

2
10 20

Sample Output 2

35

表示言語

/ /

Score : 100 points

문제

루루는 보물이 담긴 마법의 상자를 발견했다. 상자에는 서로 다른 N가지의 마법이 한 번씩 걸려 있으며, 이를 정확한 순서대로 모두 해제해야만 상자를 열 수 있다. 천재 마법사인 루루는 상자에 걸려 있는 N가지 마법의 종류는 전부 알아냈지만 해제해야 할 올바른 순서는 알지 못한다.

루루는 상자를 열기 위해 아래와 같은 방법으로 상자 열기를 시도한다.

  1. 루루는 N가지 마법 중 아직 상자에 걸려 있는 마법 하나를 선택하여 해제를 시도한다. i번째 마법을 해제 시도할 때 M_i의 마력이 소모된다.

  2. 만약 해제 시도한 마법이 순서에 맞는 마법이라면 해제에 성공한다. 순서에 맞지 않는 마법이라면 N가지 마법이 모두 걸린 상태로 되돌아간다. 해제 시도가 성공했는지 바로 알 수 있다. 해제하는 데 필요한 마법의 순서는 바뀌지 않는다.

  3. 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 種類の魔法が 1 回ずつかけられており，それらを正しい順序ですべて解除しなければ箱を開けることができない．天才魔法使いであるルルは，箱にかけられている N 種類の魔法の種類はすべて特定したが，解除すべき正しい順序は知らない．

ルルは箱を開けるため，次の方法で箱を開けようとする．

  1. ルルは N 種類の魔法のうち，まだ箱にかかっている魔法を 1 つ選び，解除を試みる．i 番目の魔法の解除を試みると，M_i の魔力が消費される．

  2. 解除を試みた魔法が順序に合う魔法なら解除に成功する．順序に合わない魔法なら，N 種類の魔法がすべてかかった状態に戻る．解除の試みが成功したかどうかはすぐに分かる．解除に必要な魔法の順序は変わらない．

  3. N 個の魔法がすべて解除されると箱が開く．

N と各魔法の消費魔力 M_i が与えられる．ルルが最適な戦略で箱を開けるとき，消費する魔力の合計の期待値を求めよ．箱を開ける正しい魔法の順序は N! 通りのうちの 1 つであり，すべての順序が正解である確率は等しい．

制約

  • 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