No.731 等差数列がだいすき

レベル : / 実行時間制限 : 1ケース 1.500秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-6}$ 以下
タグ : / 解いたユーザー数 60
作問者 : りあんりあん / テスター : ixmelixmel
0 ProblemId : 1169 / 出題時の順位表

問題文

等差数列がだいすきなりあんくんは、道端で要素数 $N$ の数列を拾いました。

りあんくんは等差数列がだいすきなので、数列の各要素の値を変更することができる数列おじいさんにお願いして、拾った数列を等差数列に変えてもらうことにしました。

ただし、数列おじいさんは数列の $i$ 番目の要素 $a_i$ を $b_i$ に変えるのにコストを $(a_i - b_i)^2$ だけ要求してきます。(かつ、各要素の値は高々1回しか変更してくれません。)

例えば、{3, 3, 4} という数列を {5, 5, 5} に変えるコストは 4 + 4 + 1 = 9、{3, 3.5, 4} に変えるコストは 0 + 0.25 + 0 = 0.25 となります。

りあんくんはできるだけ少ないコストで等差数列を得たいので、コストが最小となるような初項 $b_1$, 公差 $d$, またそのときにかかるコスト $c$ をそれぞれ求めてください。

入力

$N$
$a_1 \ a_2 \ \ldots \ a_N$

1行目に、数列の要素数 $N$ が与えられます。

続いて2行目に、数列の各要素の値 $a_i \ (1 \le i \le N)$ が空白区切りで与えられます。

入力は全て整数で、以下の制約を満たします。

  • $2 \le N \le 1000$
  • $0 \le a_i \le 10^5$

出力

1行目に、コストが最小となるような変更後の等差数列の初項 $b_1$ と公差 $d$ を空白区切りで出力してください。

2行目に、そのときにかかるコスト $c$ を出力してください。

各要素に対し、$10^{-6}$ 以下の誤差が許容されます。

最後に改行してください。

サンプル

サンプル1
入力
3
3 3 4
出力
2.83333333333333 0.5
0.166666666666667
サンプル2
入力
5
0 0 0 0 10000
出力
-2000 2000
40000000

$b_1$ はマイナスとなる可能性があります。

サンプル3
入力
7
6 5 4 3 2 1 0
出力
6 -1
0

$d$ がマイナスになったり、$c$ がゼロになる可能性があります。

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

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