No.944 煎っぞ!

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 126
作問者 : ganariyaganariya / テスター : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
12 ProblemId : 2628 / 出題時の順位表
問題文最終更新日: 2019-12-08 00:05:12

問題文

バーチャルYoutuberの卯月ロウは、コーヒー豆が大好きでした。 どれくらい好きかというと自分で豆を煎ってしまうほどです。 この世界のコーヒー豆には正の整数で表される「美味しさ度」というものがそれぞれに存在し、各豆がどれくらい美味しいかを表しています。

卯月ロウは、このコーヒー豆を合計$N$個持っており、これらは数列$a$で表されます。 左から$i$番目のコーヒー豆の美味しさ度は$a_i$で表されます。

卯月ロウは、数列$a$に含まれるコーヒー豆の美味しさ度がバラバラだと苦味が多く含まれてしまうため、 すべてのコーヒー豆の美味しさ度が等しくなるよう好きな回数だけ自由に操作を行うことにしました。

行える操作は以下のようなのものです。

  • 今の数列$a$の要素数を$K$とする。このとき、左から$i(1{\leq}i{\leq}K-1)$番目のコーヒー豆と$i+1$番目の隣り合う$2$つのコーヒー豆を煎って $1$つにする。このとき、新しくできるコーヒー豆の美味しさ度は$a_i+a_{i+1}$となる。 ただし、$K>1$のときのみ行えることに注意する(隣り合うコーヒー豆が必要であるため)。

卯月ロウは、以上の操作を繰り返しすべてのコーヒー豆の美味しさ度を等しくしながら、できるだけ操作終了時に残っているコーヒー豆の数$R$を最大にしたいです。 操作終了時に残っている最大のコーヒー豆の数$R$を求めてください。

入力

$N$
$a_1 \ a_2 \ ...\ a_N$

  • 入力はすべて整数
  • $1{\leq}N{\leq}10^5$
  • $1{\leq}a_i{\leq}10^2$

出力

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

サンプル

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

卯月ロウは$8$個のコーヒー豆を持っています。

隣接する$2$つのコーヒー豆を煎ってくっつけるという操作を繰り返すことで$a = (7, 7, 7)$という並びにでき、これが最大の操作終了時に残るコーヒー豆の数$3$となります。

すべてくっつけることで$a = (21)$にできますが、$1$つしか残らないため、答えは$3$となります。

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

最初の時点で、これ以上操作を行うことはできません。

サンプル3
入力
60
36 45 67 64 100 2 3 22 52 64 9 22 53 63 45 60 56 26 68 33 87 23 91 81 71 34 37 91 51 26 44 76 93 1 34 100 3 22 53 23 61 8 85 90 49 6 40 45 66 80 36 32 21 88 40 42 78 97 99 6 
出力
3

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