Connection Status:
Competition Arena > FencingGarden

FencingGarden

Member SRM 461 · 2009-12-03 · by dolphinigle

Member SRM 461 · 2009-12-03 · by dolphinigle · Search, Simple Math
Class Name: FencingGarden
Return Type: long
Method Name: computeWidth
Arg Types: (vector<int>)
Problem Statement

Problem Statement

There is an empty grass field with an infinitely long straight wall. You are going to create a rectangular garden against the wall. Three sides of the garden will be enclosed with a fence. The fourth side of the garden is formed by part of the wall.

You currently have some fence segments. Each side of your fence can be created by connecting some of these segments. The length of a side of the fence is equal to the sum of the lengths of the fence segments that form it. The length of each side of the fence must be exactly equal to the length of the corresponding side of the rectangular garden. As in real life, each fence segment may only be used at most once.

Fortunately, you have a saw that can cut at most one of these segments into two shorter segments. The saw will break after being used one time. You may cut the one segment into two shorter segments at any point between its endpoints (non-integer length is allowed). Note that the total length of the two shorter segments created must be equal to the length of the original segment.

You are given int[] segment. The i-th element of segment represents the length of the i-th fence segment. Using these segments construct the garden fence (as described above) enclosing the maximum area possible and return the length of the garden's side parallel to the wall. If the maximum area can be formed in more than one way then return the largest parallel-to-the-wall length that gives the maximum area.

Constraints

  • segment will contain between 2 and 40 elements, inclusive.
  • Each element of segment will be between 1 and 100,000,000, inclusive.
Examples
0)
{1,1,1,1,10}
Returns: 8

Cut the segment with length 10 into segments with lengths 2 and 8. Make two sides with length 3 and one side with length 8 using these segments. This gives a 3x8 rectangular garden. Note that a 4x6 rectangular garden can also be constructed. It has the same maximum area of 24. But the correct answer is 8 since you should return the largest parallel-to-the-wall length that gives the maximum area and 8 is larger than 6.

1)
{50,25,25}
Returns: 50

Sometimes it is not necessary to cut any segment.

2)
{5,7,9,13,21,581,1848,1058,57172,58281,612,528}
Returns: 60078
3)
{1,1}
Returns: 1
4)
{100000000,100000000}
Returns: 100000000

Submissions are judged against all 128 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class FencingGarden with a public method long long computeWidth(vector<int> segment) · 128 test cases · 2 s / 256 MB per case

Submitting as anonymous