No.77 レンガのピラミッド

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 120
作問者 : yuki2006yuki2006

4 ProblemId : 186 / 出題時の順位表

問題文

Vegaはレンガで平面ピラミッドを作りたいと考えてる。

庭には、すでに$N$列分のレンガが隙間なく積まれていて、それぞれの$i$列目の積まれている個数は$A_i$で表される。
最初の配置から、レンガをいくつか動かして、ピラミッドの配置になるように並び替えたいです。

ピラミッドの配置とは、$1$から始めて$[1,2,3,4,3,2,1]$のように中心の位置まで1ずつ増え、中心以降は1ずつ減るような配置である。
(つまり、ピラミッド配置の列数は奇数になる。)

ピラミッドとは別の場所に、捨て置き場も設けられており、ピラミッドの配置に使われなかったレンガを置くこともできる。

移動とは、任意の列の一番上にある1つのレンガを持ち、別の列に移動するか、もしくは捨て置き場に移動することである。
このとき、ピラミッド配置は、最初の配置の1列目のレンガの場所から始めるとする。

最初の配置から0個以上のレンガを移動しできるピラミッド配置への最小の移動数を求めてください。


ビラミッドの場所には1つのピラミッドのみがあるとして、不要なレンガはすべて捨て置き場に移動するとする。
レンガはどれも同じサイズの立方体であるとする。

入力

$N$
$A_1\,A_2\,\cdots\,A_N$

入力はすべて整数で与えられる。
$1\le N \le 100 $
$1\le A_i \le 100 $

出力

ピラミッド配置への最小の移動数を求めてください。
最後に改行してください。

サンプル

サンプル1
入力
5
2 2 2 1 2
出力
2

1列目のブロックを3列目に移動し、5列目のブロックを4列目に移動すると、ピラミッド配置になるので、2個のブロックを移動するとピラミッド配置になる。

サンプル2
入力
3
3 2 3
出力
4

4つのレンガを捨て置き場に移動すると、ピラミッド配置になる。

サンプル3
入力
9
1 1 1 1 1 1 1 1 1
出力
4

サンプル4
入力
3
1 2 1
出力
0

すでにピラミッド配置になっている。

サンプル5
入力
1
4
出力
3

最初が1列しかない場合でも3つ動かすことで3列のピラミッドができる。

提出ページヘ