C - 積み重ね Editorial /

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

　高橋君はもう大人なので、親元を離れて一人暮らしをすることにしました。トラックから引越し先の部屋へと荷物のダンボールを運びたいのですが、部屋の床がダンボールで埋まってしまうと、今日高橋君が寝るための布団がひけません。
　そこで、1 箱ずつ広げて置くのではなく、ある程度ダンボールを積み重ねた山を作ることにしました。しかし、ダンボールには重さが決まっており、下にあるダンボールよりも重いダンボールを上に積み重ねると下のダンボールが潰れてしまいます。
図：下にあるダンボールは上にあるダンボール以上の重さでなければならない

　トラックから運ぶ順にダンボールの重さが与えられるので、ダンボールを潰さないような積み重ね方を考えなさい。そして、その積み重ねた山の個数が最小となる場合の山の個数を求めなさい。

入力

入力は以下の形式で標準入力から与えられる。 
N
w_1
w_2
:
:
w_N
  • 入力は N+1 行ある。
  • 1 行目には、ダンボールの個数を表す整数 N(1≦N≦50) が与えられる。
  • 2 行目からの N 行には、i+1(1≦i≦N) 行目に i 番目に運ぶダンボールの重さを表す整数 w_i(1≦w_i≦100,000) が与えられる。

出力

ダンボールを順番に運び、上のダンボールが下のダンボールと同じ重さまたはそれよりも軽くなるように積み重ねたときに、できるダンボールの山の数の最小値を標準出力に 1 行で出力せよ。
なお、最後には改行を出力せよ。

入力例 1

5
4
3
1
2
1

出力例 1

2
  • 下図の例の順に積み重ねると、2 つのダンボールの山ができる。
  • 3 番目のダンボールの次に重さ 2 のダンボールをその上に重ねることはできないので 1 つの山にすることはできず、最小は 2 となる。

入力例 2

7
93
249
150
958
442
391
25

出力例 2

3
  • 下図の形に積み重ねると、山の数は 3 となる。
    • 訂正：下図の225のダンボールは25の誤りです。申し訳ありません。

入力例 3

4
100
100
100
100

出力例 3

1
  • 同じ重さのダンボールは積み重ねられるので、1 つの山にすることができる。

入力例 4

6
5
10
15
20
25
30

出力例 4

6
  • どのダンボールも前に運んだダンボールの上に重ねられないので、1 つも積み重ねることができない。
  • したがって、6 つの山が最小となる。

入力例 5

15
3
1
4
1
5
9
2
6
5
3
5
8
9
7
9

出力例 5

6
  • 下図のように積み重ねると最小となる。

Source Name

ARC 006