No.21 平均の差

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 655
作問者 : krotonkroton
6 ProblemId : 67 / 出題時の順位表
問題文最終更新日: 2015-11-14 17:49:44

問題文

\(N\)個の数字が与えられるのでこれらを\(K(\geq 3)\)個のグループに振り分ける。
ただし各グループには最低一つ数字が含まれているとする。

ex) 例えば 与えれる数字が \(\{10,3,23,91,5\}\), \(K=3\) なら
\(\{\{3,91\},\{23,5\},\{10\}\}\) のような振り分けかたはただしく
\(\{\{\},\{3,5,10\},\{23,91\}\}\) のような振り分けかたは認められません

グループごとに平均を計算し, それらをもとに 最大の平均 - 最小の平均 を計算し、
最後に小数点以下を切り上げその値を「平均の差」と呼ぶ。
平均の差を最も大きくするようなグループ分けをしたとき、平均の差はいくつになるか答えよ。

入力

\(N\)
\(K\)
\(n_1\)
\(n_2\)
\(\dots\)
\(n_N\)

\(1\)行目には\(N\ (3 \leq N \leq 9)\)が与えられる。
\(2\)行目には\(K\ (3 \leq K \leq N)\)が与えられる。
\(3\)行目~\(N+2\)行目には数字\((1 \leq n_i \leq 1000, 1 \leq i \leq N)\)が与えられる。

出力

答えの数値を文字列で出力してください。
最後に改行してください。

サンプル

サンプル1
入力
5
3
555
20
432
301
21
出力
535

例えば \(\{\{555\}, \{21,20\}, \{433,301\}\}\) のようにグループ分けすると
平均は \(\{555/1, (21+20)/2, (432+301)/2\} = \{555, 20.5, 366.5\}\) なので
最大の平均 - 最小の平均は \(555-20.5 = 534.5\)
最後に小数点以下を切り上げて\(535\)

サンプル2
入力
8
4
329
980
656
738
739
542
873
501
出力
651

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。