Problem Statement

While building a tower, workers want to lift boxes up from the ground floor to the top floor using elevators. There are two types of boxes. Each box has a weight 50 or 100. Each elevator has enough space for up to two boxes, and can carry a maximum combined weight of 150. Each elevator can only be used once. Given a int[] boxWeights containing the weight of each box, return the minimum number of elevators necessary to transport all the boxes.

Definition

Class:              TowerLifts
Method:             leastNumber
Parameters:         int[]
Returns:            int
Method signature:   int leastNumber(int[] boxWeights)
(be sure your method is public)

Constraints

• boxWeights will contain between 1 and 50 elements, inclusive.
• Each element of boxWeights will be equal to 50 or 100.

Examples

0)

{50, 100, 50, 50, 50}
Returns: 3
There are two boxes in the first elevator: 50, 100. The second elevator contains: 50 and 50. The third elevator contains only one box: 50.

1)

{100, 100, 50, 100}
Returns: 3

2)

{50, 50}
Returns: 1

3)

{50, 50, 100, 100}
Returns: 2

4)

{50, 50, 100, 100, 50, 100, 50, 50, 50}
Returns: 5

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.