AT_abc003_3 [ABC003C] AtCoderプログラミング講座

[problemUrl]: https://atcoder.jp/contests/abc003/tasks/abc003_3 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} $ 以下であれば許容される。 また、出力の末尾には改行を入れること。 ```

2 2
1000 1500
```

 ```
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 1
1000 1500
```

 ```
750
```

- このケースでは高橋くんは $ 1 $ 個の講座動画しか見ることができません。
- レート $ 1500 $ の競技プログラマーの講座動画を見るのが最適です。
 
```
10 5
2604 2281 3204 2264 2200 2650 2229 2461 2439 2211
```

 ```
2820.031250000
```
                            

N/A

N/A