C - 収納
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 300 点
問題文
N 本の棒があり、 i(1≦i≦N) 本目の棒の長さは L_i です。
これらを長さ C のケースに収納していきます。
ケースには 1 本か 2 本の棒を収納できますが、棒を収納できる条件は
- 1 本の棒を収納するには、棒の長さが a のとき、 a≦C
- 2 本の棒を収納するには、棒の長さが a,b のとき、 a+b+1≦C
です。
全ての棒を収納するのに、ケースは最小でいくつ必要か答えてください。
制約
- 1≦N≦100000
- 1≦C≦10^9
- 1≦L_i≦C
- 入力は整数からなる
入力
入力は以下の形式で標準入力から与えられる。
N C L_1 : L_N
出力
ケースが最小で x 個必要な時、 x を出力せよ。
入力例 1
4 10 2 8 4 5
出力例 1
3
3 番目の棒と 4 番目の棒を同じケースに収納し、 1 番目の棒と 2 番目の棒をそれぞれ別のケースに収納すると、 3 個のケースに収納することができます。
入力例 2
3 10 1 1 1
出力例 2
2
1 つのケースには 2 本までの棒しか収納できないことに注意して下さい。
入力例 3
9 30 22 5 2 18 6 21 29 11 18
出力例 3
5