C - AtCoderプログラミング講座 Editorial /

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

AtCoder社では、優秀な競技プログラマーの講座動画を N 個配信しています。
初心者競技プログラマーの高橋くんは、AtCoder社が配信している動画を見て修練しようとしています。
高橋くんの実力はレートという実数値で表され、レートが高いほど実力が高いことを表します。

高橋くんのレートが C の時に、レート R の競技プログラマーの講座動画を見ると、高橋くんのレートは (C+R)/2 に変化します。
高橋くんは、講座動画を合計で K 個まで好きな順番で見ることができますが、同じ競技プログラマーの講座動画は一度までしか見ることができません。
講座動画を配信している N 人のレートが与えられた時、高橋くんが講座動画を見ることによって達成できるレートの最大値を求めるプログラムを書いてください。
ただし、高橋くんの初期レートは 0 です。

入力

入力は以下の形式で標準入力から与えられる。 
N K
R_1 R_2 ... R_N
  1. 1 行目には、講座動画の数を表す整数 N\ (1 ≦ N ≦ 100) と高橋くんが見ることのできる動画の数を表す整数 K\ (1 ≦ K ≦ N) がスペース区切りで与えられる。
  2. 2 行目には、講座動画を配信している競技プログラマーのレートを表す整数 R_i\ (1 ≦ R_i ≦ 4,000) がスペース区切りで与えられる。

出力

高橋くんが達成できる最大レートを 1 行で出力せよ。
絶対誤差、または、相対誤差が 10^{-6} 以下であれば許容される。
また、出力の末尾には改行を入れること。

入力例 1

2 2
1000 1500

出力例 1

1000.000000
  • 以下の方法が最適です。
    • まず、レート 1000 の競技プログラマーの講座動画を見ます。これにより、高橋くんはレート 0 から (0+1000)/2 = 500 になります。
    • 次に、レート 1500 の競技プログラマーの講座動画を見ます。これにより、高橋くんはレート 500 から (500+1500)/2 = 1000 になります。
  • しかし、例えば、以下の方法は最適ではありません。
    • まず、レート 1500 の競技プログラマーの講座動画を見ます。これにより、高橋くんはレート 0 から (0+1500)/2 = 750 になります。
    • 次に、レート 1000 の競技プログラマーの講座動画を見ます。これにより、高橋くんはレート 750 から (750+1000)/2 = 875 になります。

入力例 2

2 1
1000 1500

出力例 2

750
  • このケースでは高橋くんは 1 個の講座動画しか見ることができません。
  • レート 1500 の競技プログラマーの講座動画を見るのが最適です。

入力例 3

10 5
2604 2281 3204 2264 2200 2650 2229 2461 2439 2211

出力例 3

2820.031250000