問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 1.500秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-6}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 136
作問者 : りあんりあん / テスター : ixmelixmel
3 ProblemId : 1169 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-09-07 17:19:49

問題文

等差数列がだいすきなりあんくんは、道端で要素数 $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$ がゼロになる可能性があります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。