ANewFence
SRM 851 · 2023-12-06 · by misof
Problem Statement
You want to make a new wooden fence.
You have some scrap wood. You would like to use some of it as the planks in the fence.
All planks in the fence need to have exactly the same length.
If you have two shorter pieces of wood that together have the correct length, you can nail them together and use them as a single plank.
You cannot combine more than two pieces of wood into a plank (the fence wouldn't be sturdy enough) and you cannot shorten the pieces you have (you only have a hammer and nails, but no saw).
You are given the
You want to make the longest fence possible. I.e., you want to maximize the number of planks. You can choose the height of your fence (i.e., the length of all planks that form it) and you can also choose how to combine the pieces of wood in your collection. Return the maximum number of planks in your fence.
Constraints
- wood will contain between 1 and 200 elements, inclusive.
- Each element of wood will be between 1 and 10^9, inclusive.
{10, 10, 10, 10, 4, 10, 7, 10}
Returns: 6
The optimal fence height is 10. We have six pieces of wood that can be used as planks. The pieces with lengths 4 and 7 will remain unused.
{10, 10, 10, 10, 4, 10, 6, 10}
Returns: 7
As in the previous example, the optimal fence height is 10. However, now we can combine the two shorter pieces of wood into the seventh plank for the fence: 4+6 = 10.
{10, 10, 10, 10, 3, 10, 3, 4, 10}
Returns: 6
Remember that we cannot make planks for the fence from more than two pieces of wood. In particular, here we cannot use the pieces with lengths 3, 3, 4 to form a plank for the fence.
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Returns: 5
The optimal fence height is either 10 or 11. In both cases we can assemble five planks.
{10, 110, 100, 100, 10}
Returns: 3
We can use everything we have to make three planks of length 110 each.
{5, 5, 10}
Returns: 2
You can either have two planks of length 5, or combine the two shorter pieces and have two planks of length 10. Both solutions are optimal.
{3, 7, 8, 2, 4, 6, 5, 5, 5, 5}
Returns: 5
Here, pairing up the pieces in the given order gives us five planks of length 10. Alternately, we can build a fence using the four pieces of length 5 as planks and making the fifth plank as 2+3.
Submissions are judged against all 93 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ANewFence with a public method int build(vector<int> wood) · 93 test cases · 2 s / 256 MB per case