PROBLEM STATEMENT
It's moving day, and the movers are stacking your stuff in their truck. But now
it's reached the point where there's only room left for one stack of items, so
all the items that are left have to be stacked on top of each other to form a
single monolithic column. Every object has two properties associated with it: a
weight (in pounds), and a strength - that is, a certain number of pounds of
weight that can be placed on top of it without breaking it. Given the weights
and strengths for a set of items, find the number of ways the movers can stack
them in the truck without breaking them. If it cannot be done without breaking
something, return 0 (and sue the movers for damages).
DEFINITION
Class: Movers
Method name: stack
Parameters: String[]
Return type: int
Method signature: int stack(String[] items); (be sure your method is public)
Each String in objects has the following format:
"<weight> <strength>"
where <weight> is an integer from 1 to 200 inclusive, and <strength> is an
integer from 0 to 1000 inclusive. <weight> and <strength> are separated by a
single space. Quotes and angle brackets are included for clarity; they do not
appear in the String.
NOTES
* In every valid configuration of the stack, each item must be able to support
the combined weight of all the items that are above it in the stack in order to
avoid breakage (just like the real world).
Topcoder will ensure that:
- Items will contain from 1 to 12 elements inclusive.
- Each element of items will be formatted as a pair of integers separated by a
single space, as described above.
- The first integer of each element will be in the range 1 to 200 inclusive.
- The second integer of each element will be in the range 0 to 1000 inclusive.
- Integers will not contain leading zeros, and a value of zero will be
represented by a single zero (as in "0").
EXAMPLES
objects: ["10 20","10 10","10 0"]
return value: 1
In this case, there are three items to be stacked, each with a weight of 10
pounds. The item with 0 strength must be on top because it cannot hold any
weight without breaking. The item with a strength of 20 must go on the bottom
because it is the only one that can hold the combined weight of the other two.
The remaining item, then, must go in-between. There is only one way to stack
these items, therefore the return value is 1.
objects: ["10 20","10 0","10 0"]
return value: 0
In this case, there are two items that cannot hold any weight without breaking.
Since only one item can be on top (there is only one stack), there is no way to
stack these items without breakage, so return 0.
objects: ["10 10","10 10","10 0"]
return value: 0
Here, there is no item strong enough to hold the combined weight of the other
two, so none of the items can go on the bottom without breaking. Again, return 0.
objects: ["10 20","10 25","10 0"]
return value: 2
objects: ["10 20","10 30","10 10"]
return value: 4