/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 300 点
問題文
あなたは鍋と N 個の具材を持っています。各具材は 価値 と呼ばれる実数の値を持ち、i 個目 (1 \leq i \leq N) の具材の価値は v_i です。
2 個の具材を鍋に入れると、それらは消滅して新たに 1 個の具材が生成されます。この新たな具材の価値は元の 2 個の具材の価値を x, y として (x + y) / 2 であり、この具材を再び鍋に入れることもできます。
この具材の合成を N - 1 回行うと、最後に 1 個の具材が残ります。この具材の価値として考えられる最大の値を求めてください。
制約
- 2 \leq N \leq 50
- 1 \leq v_i \leq 1000
- 入力中の値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N v_1 v_2 \ldots v_N
出力
最後に残る 1 個の具材の価値として考えられる最大の値を表す小数 (または整数) を出力せよ。
出力は、ジャッジの出力との絶対誤差または相対誤差が 10^{-5} 以下のとき正解と判定される。
入力例 1
2 3 4
出力例 1
3.5
はじめに持っている具材が 2 個の場合、それらをともに鍋に入れるほかありません。価値 3, 4 の具材から合成される具材の価値は (3 + 4) / 2 = 3.5 です。
なお、3.50001, 3.49999 などと出力しても正解となります。
入力例 2
3 500 300 200
出力例 2
375
今回ははじめに 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 の具材が合成される。
よって、最後に残る 1 個の具材の価値として考えられる最大の値は 375 です。
なお、375.0 などと出力しても正解となります。
入力例 3
5 138 138 138 138 138
出力例 3
138
Score : 300 points
Problem Statement
You have a pot and N ingredients. Each ingredient has a real number parameter called value, and the value of the i-th ingredient (1 \leq i \leq N) is v_i.
When you put two ingredients in the pot, they will vanish and result in the formation of a new ingredient. The value of the new ingredient will be (x + y) / 2 where x and y are the values of the ingredients consumed, and you can put this ingredient again in the pot.
After you compose ingredients in this way N-1 times, you will end up with one ingredient. Find the maximum possible value of this ingredient.
Constraints
- 2 \leq N \leq 50
- 1 \leq v_i \leq 1000
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N v_1 v_2 \ldots v_N
Output
Print a decimal number (or an integer) representing the maximum possible value of the last ingredient remaining.
Your output will be judged correct when its absolute or relative error from the judge's output is at most 10^{-5}.
Sample Input 1
2 3 4
Sample Output 1
3.5
If you start with two ingredients, the only choice is to put both of them in the pot. The value of the ingredient resulting from the ingredients of values 3 and 4 is (3 + 4) / 2 = 3.5.
Printing 3.50001, 3.49999, and so on will also be accepted.
Sample Input 2
3 500 300 200
Sample Output 2
375
You start with three ingredients this time, and you can choose what to use in the first composition. There are three possible choices:
- Use the ingredients of values 500 and 300 to produce an ingredient of value (500 + 300) / 2 = 400. The next composition will use this ingredient and the ingredient of value 200, resulting in an ingredient of value (400 + 200) / 2 = 300.
- Use the ingredients of values 500 and 200 to produce an ingredient of value (500 + 200) / 2 = 350. The next composition will use this ingredient and the ingredient of value 300, resulting in an ingredient of value (350 + 300) / 2 = 325.
- Use the ingredients of values 300 and 200 to produce an ingredient of value (300 + 200) / 2 = 250. The next composition will use this ingredient and the ingredient of value 500, resulting in an ingredient of value (250 + 500) / 2 = 375.
Thus, the maximum possible value of the last ingredient remaining is 375.
Printing 375.0 and so on will also be accepted.
Sample Input 3
5 138 138 138 138 138
Sample Output 3
138