問題一覧 > 通常問題

No.944 煎っぞ!

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 192
作問者 : ganariya / テスター : nmnmnmnmnmnmnm
17 ProblemId : 2628 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-12-08 00:05:12

問題文

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

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

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

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

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

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

入力

N
a1 a2 ... aN

  • 入力はすべて整数
  • 1N105
  • 1ai102

出力

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

サンプル

サンプル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、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。