/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 433 点
問題文
高橋君は引っ越し業者でアルバイトをしています。今日の仕事は、マンションの 1 階にある N 個の荷物を、エレベーターを使ってすべて同じ目的階まで運ぶことです。
各荷物 i（1 \leq i \leq N）には重さ W_i キログラムが設定されています。このマンションのエレベーターには、一度に積載できる荷物の重さの合計の上限 C キログラムがあります。高橋君はエレベーターに同乗して荷物を運びますが、高橋君自身の体重は積載上限には含まれません。
高橋君は効率よく作業を終わらせるため、N 個の荷物をいくつかのグループに分け、グループごとにまとめてエレベーターで運ぶことにしました。ここで、各荷物はちょうど 1 つのグループに属し、各グループには 1 個以上の荷物が含まれるものとします。また、各グループに含まれる荷物の重さの合計は C キログラム以下でなければなりません。
1 回の運搬では、1 つのグループに属する荷物をすべてエレベーターに積み、1 階から目的階まで運びます。次のグループを運ぶ際には、高橋君は空のエレベーターで 1 階に戻ります。運搬回数はグループの数に等しくなります。
すべての荷物を運び終えるために必要な最小の運搬回数を求めてください。
なお、すべての荷物の重さは積載上限 C 以下であることが保証されているため、どの荷物も単独で運ぶことができます。
制約
- 1 \leq N \leq 15
- 1 \leq C \leq 10^9
- 1 \leq W_i \leq C（1 \leq i \leq N）
- 入力は全て整数
入力
N C W_1 W_2 \ldots W_N
- 1 行目には、荷物の個数 N と、エレベーターの積載上限 C が、スペース区切りで与えられる。
- 2 行目には、各荷物の重さ W_1, W_2, \ldots, W_N が、スペース区切りで与えられる。
出力
すべての荷物を運ぶために必要な最小の運搬回数を 1 行で出力せよ。
入力例 1
3 10 4 5 6
出力例 1
2
入力例 2
5 100 30 50 40 20 60
出力例 2
2
入力例 3
8 1000 200 300 150 400 250 100 350 450
出力例 3
3
Score : 433 pts
Problem Statement
Takahashi is working a part-time job at a moving company. Today's task is to transport N packages from the 1st floor of an apartment building to a single destination floor using an elevator.
Each package i (1 \leq i \leq N) has a weight of W_i kilograms. The elevator in this apartment building has a maximum total weight capacity of C kilograms for the packages loaded at one time. Takahashi rides the elevator alongside the packages to transport them, but his own body weight is not counted toward the weight capacity.
To finish the work efficiently, Takahashi decided to divide the N packages into several groups and transport each group together using the elevator. Here, each package belongs to exactly one group, and each group contains at least one package. Additionally, the total weight of the packages in each group must be at most C kilograms.
In one trip, Takahashi loads all packages belonging to one group onto the elevator and transports them from the 1st floor to the destination floor. To transport the next group, Takahashi returns to the 1st floor with the empty elevator. The number of trips equals the number of groups.
Find the minimum number of trips required to transport all the packages.
Note that it is guaranteed that the weight of every package is at most C, so any single package can be transported on its own.
Constraints
- 1 \leq N \leq 15
- 1 \leq C \leq 10^9
- 1 \leq W_i \leq C (1 \leq i \leq N)
- All inputs are integers
Input
N C W_1 W_2 \ldots W_N
- The first line contains the number of packages N and the elevator's weight capacity C, separated by a space.
- The second line contains the weights of each package W_1, W_2, \ldots, W_N, separated by spaces.
Output
Print the minimum number of trips required to transport all the packages, on a single line.
Sample Input 1
3 10 4 5 6
Sample Output 1
2
Sample Input 2
5 100 30 50 40 20 60
Sample Output 2
2
Sample Input 3
8 1000 200 300 150 400 250 100 350 450
Sample Output 3
3